[BOJ] Python 플로이드(11404)

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

 

 

대표적인 플로이드 워셜 문제이다. 

모든 경로에서의 최단경로를 출력하는 문제이다.

 

3중 for 문을 통해 값을 최신화 한다.

 

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
graph = [[] for _ in range(N+1)]
distance = [[float('inf')]*(N+1) for _ in range(N+1)]

for i in range(1, N+1):
    distance[i][i] = 0

for _ in range(M):
    s,e,cost = map(int,input().split())
    if distance[s][e] > cost:
        distance[s][e] = cost

def floyid_func():

    for k in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                if distance[i][j] > distance[i][k] + distance[k][j]:
                    distance[i][j] = distance[i][k] + distance[k][j]

floyid_func()


for i in range(1,N+1):
    for j in range(1,N+1):
        if distance[i][j] == float('inf'):
            distance[i][j] = 0

        print(distance[i][j],end=' ')
    print()

 

회고.

자기 자신은 0이라는 조건을 잊어버려 답이 나오지 않았었다....