[백준] 11404번 플로이드 파이썬 코드

코드

import sys
input = sys.stdin.readline
inf = 987654321 # 무한대를 의미
n = int(input()) # 노드
e = int(input()) # 간선
graph = [[inf]*(n+1)for _ in range(n+1)]

for _ in range(e):
  x,y,z = map(int, input().split())
  graph[x][y]=min(z, graph[x][y]) # 가중치가 낮은 것을 선택

# 플로이드 워셜 알고리즘 사용 (모든 정점에서 모든 정점으로 가는 가중치 계산)
# dij = min(Dij, dik + dkj) (플로이드 워셜 점화식)

for i in range(1,n+1): # 중간에 들러야 하는 것이 가장 위에 있어야 한다
  for j in range(1,n+1):
    for k in range(1,n+1):
      if j == k: graph[j][k] = 0 # 만약 값이 같으면 0
      graph[j][k] = min(graph[j][k], graph[j][i]+graph[i][k])

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:])

 

플로이드 워셜 알고리즘에 대해 이해할 수 있던 문제였다.