[백준 11404번] 플로이드 (Python3)

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번 때렸다 ㅋㅋ

 

통과하긴 했는데, 앞으로 또 어떤 문제가 나올지 모르니 플로이드 알고리즘도 공부해야겠다.

 

 

 

오늘의 교훈) 플로이드 알고리즘을 공부하자