Jinho Tech

기본적인 플로이드-와샬 문제이다. 

import sys
INF = sys.maxsize
input = sys.stdin.readline

n, m = int(input()), int(input())
dis = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    if c < dis[a-1][b-1]:
        dis[a-1][b-1] = c
for k in range(n):
    for a in range(n):
        for b in range(n):
            if a != b:
                dis[a][b] = min(dis[a][b], dis[a][k]+dis[k][b])
for i in range(n):
    for j in range(n):
        if dis[i][j] == INF:
            dis[i][j] = 0
for t in dis:
    print(*t)

BFS 문제이다. res.append(sum(check)-N)이 포인트인 것 같다. 

from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in grpah[node]:
            if check[n] == 0:
                check[n] = check[node]+1
                queue.append(n)
    
N, M = map(int, input().split())
grpah = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    grpah[u].append(v)
    grpah[v].append(u)
res = []
for i in range(1, N+1):
    check = [0]*(N+1)
    check[i] = 1
    bfs(i)
    res.append(sum(check)-N)
print(res.index(min(res))+1)