[알고리즘][Python] 백준(BOJ) 11404 플로이드_파이썬

 

11404 플로이드    www.acmicpc.net/problem/11404

11404번: 플로이드

 

 

 

문제 풀기 전 공부할 것 : 플로이드-와샬

 

 

 

 

 

 

 

풀이

<내용>

• 최소 비용을 구하는 문제로 플로이드 와샬을 이용해서 해결하면 된다.
• 도시 a에서 도시 b로 가는 비용을 초기화한다.
• 그리고 3중 for문을 통해 i에서 j로 갈 때 k 도시를 거쳐서 가는 경우가 최소 비용이면 이를 업데이트한다.

 

 

<코드>

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
INF = 987654321
city = [[INF for _ in range(n)] for _ in range(n)]
for _ in range(m):
    i, j, cost = map(int, input().split())
    city[i-1][j-1] = min(city[i-1][j-1], cost)
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            city[i][j] = min(city[i][j], city[i][k]+city[k][j])
            
for row in city:
    for i in range(n):
        if row[i] == INF:
            row[i] = 0
    print(*row)