[백준/python/11404] 플로이드

문제링크 : 플로이드

단순히 최소비용을 구하는 문제인줄 알았는데 플로이드-와샬이라는 알고리즘을 사용하는 문제였다.
플로이드-와샬에 대해서는 처음 접하게되었다.
플로이드-와샬 알고리즘은 하나의 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다.

import sys
input=sys.stdin.readline

n=int(input())
m=int(input())
inf=sys.maxsize

cost=[[inf]*n for i in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    if cost[a-1][b-1]>c:
        cost[a-1][b-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i!=j and cost[i][j]>cost[i][k]+cost[k][j]:
                cost[i][j]=cost[i][k]+cost[k][j]
for i in cost:
    for j in i:
        if j==inf:
            print(0,end=' ')
        else:
            print(j,end=' ')
    print()

i부터 j까지 가는 방법에서 k라는 중간값을 넣어준다.
중간값을 거쳐가는 (i->k로 가는 비용)+(k->j로 가는 비용) 을 모두 비교하여 최소비용을 찾아준다.