문제링크

설명

예시된 그래프에서 굵게 표시된 1, 2, 3, 4, 5, 6은 집하장을 나타낸다.

정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간이다.

이로부터 얻어내야 하는 경로표는 다음과 같다.

경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다.

예를 들어 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.

아이디어

다익스트라는 어떤 노드에서 다른 모든 노드에 대한 최단 경로(가중치)를 찾는 알고리즘이라고 생각함

따라서 모든 노드에서 모든 노드에 대한 최단 경로(가중치)를 찾아야 하는 이 문제는 워셜이 좀더 적절하다고 판단

시간 복잡도

플로이드-워셜 알고리즘의 시간 복잡도는 O(N^3)

코드

n, m = map(int, input().split())

distance = [[int(1e9)] * (n + 1) for _ in range(n + 1)]

graph = [[i for i in range(n + 1)] for _ in range(n + 1)]

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

for _ in range(m):
    a, b, c = map(int, input().split())
    distance[a][b] = min(distance[a][b], c)
    distance[b][a] = min(distance[b][a], c)

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

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