[백준] 1389번-(Python 파이썬) - Floyd-Warshall

문제링크 : https://www.acmicpc.net/problem/1389

이번 문제도 플로이드 와샬 알고리즘으로 풀었다.
사람이라 생각하지 않고 앞에서 많이 풀어왔던 도시와 다리라고 생각하면 금방 이해가 된다.
각각의 최단경로를 구한 다음, 경로를 다 합쳤을 때 가장 작은 사람을 출력하면 된다.

import sys

input = sys.stdin.readline
inf = sys.maxsize

n, m = map(int, input().split())

graph =[[inf] * n for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                graph[i][j] = 0
            elif graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]
sum = [0] * n
ans = inf
for i in range(n):
    for j in range(n):
        sum[i] += graph[i][j]
    if ans > sum[i]:
        ans = sum[i]
        result = i
        
print(result + 1)