[백준- 파이썬] 11404: 플로이드

플로이드-워샬 알고리즘으로 풀었는데 처음에는 답이 안나왔다.

주의! 아래 코드는 정답 아님.

import sys

input = sys.stdin.readline


def FW():
    for k in range(1, N + 1):  # 경유지
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])


INF = 100 * 100000 + 1

N = int(input())
M = int(input())

distance = [[INF] * (N + 1) for _ in range(N + 1)]

# 초기화(자기 자신으로 갈 때 0)
for i in range(1, N + 1):
    distance[i][i] = 0

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

FW()

for i in range(1, N + 1):
    for j in range(1, N + 1):
        tmp = distance[i][j]
        if tmp == 10000001:
            tmp = 0
        print(tmp, end=' ')
    print()

s, e, cost를 입력 받아서
distance[s][e]에 넣어줄 때 distance[s][e] = cost로 해서 그런 것이었다..
예를 들어서 시작점 1, 도착점 4인데 비용이 1로 들어오고, 나중에 시작점 1, 도착점 4인데 비용이 3으로 들어오면?
1에서 3 갈 때 비용이 3으로 저장된 것이다.
가장 적은 비용이 저장되어 있어야 했는데!!

distance[s][e] = min(distance[s][e], cost) 로 했더니 맞았다!