[백준] 11404 파이썬(python) : 플로이드

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

11404번: 플로이드

 

 

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
INF = (1e9)
graph = [ [INF] *(n+1) for _ in range(n+1) ]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0

for i in range(m):
    s, e, c = map(int, sys.stdin.readline().split())
    if graph[s][e] > c: #1
        graph[s][e] = c

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(1, n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            print(0, end=' ')
        else:    
            print(graph[i][j], end=' ')
    print()

 

플로이드 워셜 알고리즘 문제이다.

서로 갈수 없는 노드사이의 값을 무한으로 표시하는데 이 문제에선 무한대신 0으로 출력하기를 원하고 있다.

문제의 제약조건을 확인해 봐야하는데 "시작도시에서 도착도시로 가는 노선은 하나가 아닐 수 있습니다." 이 부분 때문에 #1을 넣어줘야 한다. 예제 입력에서도 3 4 1과 3 4 2가 나오는데 3 4 2가 늦게 나오므로  #1이 없으면 최소값을 저장해 주지 못한다.