import sys
input = sys.stdin.readline
from collections import deque
import heapq
INF = sys.maxsize
N = int(input())
M = int(input())
bus = [[INF]*(N+1) for i in range(N+1)]
dij = [[INF]*(N+1) for i in range(N+1)]
for i in range(M):
x1,x2,w = map(int,input().split())
if bus[x1][x2] > w:
bus[x1][x2] = w
def Dijkstra(start):
hq = []
heapq.heappush(hq,(0,start))
while hq:
w,now = heapq.heappop(hq)
if dij[start][now] <= w:
continue
dij[start][now] = w
for i in range(1,N+1):
heapq.heappush(hq,(bus[now][i]+w,i))
for i in range(1,N+1):
Dijkstra(i)
for i in range(1,N+1):
for j in range(1,N+1):
result = dij[i][j]
if result > 1000000000:
print(0,end=" ")
else:
print(result,end=" ")
print()
플로이드 워셜 알고리즘 관련 문제이다. 문제 제목에서 대놓고 알려주고있다..
근데 나는 플로이드 워셜 알고리즘을 몰라서 그냥 다 익스트라 알고리즘 n번 때렸다 ㅋㅋ
통과하긴 했는데, 앞으로 또 어떤 문제가 나올지 모르니 플로이드 알고리즘도 공부해야겠다.
오늘의 교훈) 플로이드 알고리즘을 공부하자