11404 플로이드 파이썬

기본 플로이드 알고리즘 사용하면 답이 안나오는 이유는 입력값에서 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다는 문구 때문이다.

import sys

input = sys.stdin.readline
cities = int(input())
busses = int(input())
INF = int(1e9)
graph = [[INF for _ in range(cities + 1)] for __ in range(cities + 1)]

# 도착 지점이 제자리일 경우 0
for i in range(1, cities + 1):
    for j in range(1, cities + 1):
        if i == j:
            graph[i][j] = 0

# f: from, t: to, c: cost
for _ in range(busses):
    f, t, c = map(int, input().split())
    graph[f][t] = min(c, graph[f][t]) # 기본 플로이드에서 추가한 부분 여러 노선 중 작은 것으로 선택

# 각 노선을 경유하는 것을 비교해서 더 작은 것을 저장
for k in range(1, cities + 1):
    for a in range(1, cities + 1):
        for b in range(1, cities + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

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