[백준/파이썬/최단경로] 16주차 문제풀이 #11404 플로이드

🔗https://www.acmicpc.net/problem/11404

딱 플로이드-워셜 알고리즘의 정석
기억하자!
플로이드-워셜은
모든 노드에서 다른 모든 노드까지의 최단 경로
다익스트라는
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로
플로이드-워셜은 점화식만 인지하고 있으면 쉽게 풀 수 있을 것 같다.
꼭 외워놔야 할듯...

import sys

INF=int(1e9)

n=int(sys.stdin.readline().rstrip())
m=int(sys.stdin.readline().rstrip())

graph=[[INF]*(n+1) for _ in range(n+1)]

for a in range(1, n+1):
    for b in range(1, n+1):
        if a==b:
            graph[a][b]=0
            
for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    #중복일 경우 최소의 비용을 업데이트
    if c<graph[a][b]:
        graph[a][b]=c

for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1,n+1):
            graph[a][b]=min(graph[a][b],graph[a][k]+graph[k][b])
            
for a in range(1,n+1):
    for b in range(1,n+1):
        if graph[a][b]==INF:
            print("0", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()