이번 문제는 플로이드-와샬 알고리즘을 통해 해결하였다. 이전 같았다면 모든 정점에서의 다익스트라 알고리즘을 돌렸겠지만 이는 분명히 시간 초과가 발생했을 것이다. 플로이드-와샬은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로 다이나믹 프로그래밍을 기초로 한다. 기본적인 틀은 다음과 같다.

for k in range(n): # k: 경유지
	for i in range(n): # i: 출발 정점
    	for j in range(n): # j: 도착 정점
        	dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j])

플로이드-와샬 알고리즘을 이용하여 이 문제를 쉽게 해결할 수 있었다.

• n을 입력받는다.
• m을 입력받는다.
• INF에 최댓값을 저장한다.
• 모든 정점에서 모든 정점까지의 거리를 저장할 리스트 graph를 2차원 리스트로 선언하고 INF로 채운다.
• m번 반복하는 for문을 돌린다.
  -> a, b, c를 입력받는다.
  -> graph[a][b]를 graph[a][b]와 c 중 더 작은 값으로 갱신한다.
• 1부터 n까지 반복하는 k에 대한 for문을 돌린다.
  -> graph[k][k]를 0으로 갱신한다.
  -> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  --> 1부터 n까지 반복하는 j에 대한 for문을 돌린다.
  ---> graph[i][j]를 graph[i][j]와 graph[i][k]+graph[k][j] 중 더 작은 값으로 갱신한다.
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 1부터 n까지 반복하는 j에 대한 for문을 돌린다.
  --> graph[i][j]가 INF일 경우, graph[i][j]를 0으로 갱신한다.
  -> graph[i][1:]을 언팩킹하여 출력한다.

Code

import sys
input=sys.stdin.readline
n=int(input())
m=int(input())
INF=sys.maxsize
graph=[[INF]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c=map(int, input().split())
    graph[a][b]=min(graph[a][b], c)
for k in range(1, n+1):
    graph[k][k]=0
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j]=min(graph[i][j], graph[i][k]+graph[k][j])
for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j]==INF:
            graph[i][j]=0
    print(*graph[i][1:])