BOJ 11404번: 플로이드

www.acmicpc.net/problem/11404

11404번: 플로이드

아이디어:

플로이드 와샬 알고리즘을 구현하여 쉽게 풀 수 있는 문제인 건 알겠는데, 왜 시작도시와 도착도시가 같은 경우에는 경유해서 갈 수 있어도 무조건 0을 출력해야 하는 건 지 이해가 안간다. 내가 문제 이해를 잘 못하는 건가.

예를 들어 문제 예시에 1 3 3이 있고 3 1 8 도 있는데 그렇다면 1 3 3 버스를 타고 1번에서 3번으로 이동하고, 다시 3 1 8버스를 타고 3번에서 1번으로 이동하여 결국 1번에서 출발해서 다시 1번으로 돌아오는 경로가 있다고 할 수 있는 거 아님? 왜 안된다는 건지..ㅋㅋ 이것때매 머리 깨지는 줄 알았다. 그냥 무조건 안되는 건가본데.. 짜증난다..

 

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
INF = 10**9
cost = [[INF]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    cost[a][b] = min(cost[a][b], c)

for k in range(1,n+1):

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

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