Q37. 플로이드

11404번: 플로이드 (acmicpc.net)

11404번: 플로이드

 

전 포스팅에서 만들어 놓은 함수로 날먹을 쓱싹 해보려고 했더니 여기엔 새로운 개념이 하나 끼어있다. 한 도시에서 다른 도시로 이동하는 버스 개수가 하나가 아닐 수 있다는 것. 그래서 입력을 받는 동시에 cost의 min값을 갱신해줘야된다.

 

안보고 다시 구현해볼겸 그냥 풀어보자. 어차피 구현 난이도도 낮으니..

 

n = int(input())
m = int(input())

INF = 1e10
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    src, dst, cost = map(int, input().split())
    graph[src][dst] = min(graph[src][dst], cost)

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

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

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("")