이번 문제는 플로이드-와샬 알고리즘을 통해 해결하였다. 기존의 플로이드-와샬 문제와 다른 점이 있다면 최단 거리를 저장하는 것이 아닌, 최단 거리로 가기 위해 다음에 방문해야할 정점의 번호를 저장해야 한다는 점이었다. 그래서 최단 거리를 저장할 리스트와 다음에 방문해야 할 정점의 번호를 저장할 리스트를 따로 만들었다.

그리고 간선의 정보를 입력받을 때에, a->b에 대한 입력이라면 다음 방문 정점 리스트를 [a][b]=b, [b][a]=a로 갱신해주어야 한다. 그리고 플로이드-와샬 알고리즘을 사용하여 각 정점까지의 최단 거리를 구하는데, 이때 다른 정점을 거쳐 가는 것의 거리가 더 짧을 경우에 최단 거리를 갱신하면서 다음 방문 정점 리스트도 갱신해주어야 한다. 예를 들어, a->b보다 a->c->b가 더 짧을 경우에, 다음 방문 정점 리스트 [a][b]를 다음 방문 정점 리스트 [a][c]의 값으로 갱신해주어야 한다. 이 과정을 거치면 다음에 방문할 정점에 대한 리스트가 완성되는데, 한번의 반복문을 통해 출발, 도착 정점이 같은 부분을 - 로 갱신해준 뒤에 언팩킹하여 한 줄을 출력해주는 방식으로 결과 리스트를 출력하였다.

• n, m을 입력받는다.
• INF에 최댓값을 저장한다.
• 최단 거리를 저장할 리스트 graph를 (n+1)*(n+1) 크기로 선언하고, INF를 채워준다.
• 다음 방문할 정점을 저장할 리스트 answer를 (n+1)*(n+1)로 선언하고, 0으로 채워준다.
• m번 반복하는 for문을 돌린다.
  -> a, b, c를 입력받는다.
  -> graph[a][b]를 graph[a][b]와 c 중 더 작은 값으로 갱신한다.
  -> graph[b][a]를 graph[b][a]와 c 중 더 작은 값으로 갱신한다.
  -> answer[a][b]를 b로 갱신한다.
  -> answer[b][a]를 a로 갱신한다.
• 1부터 n까지 반복하는 k에 대한 for문을 돌린다.
  -> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  --> 1부터 n까지 반복하는 j에 대한 for문을 돌린다.
  ---> 만약 graph[i][j]가 graph[i][k]+graph[k][j]보다 클 경우,
  ----> graph[i][j]를 graph[i][k]+graph[k][j]로 갱신한다.
  ----> answer[i][j]를 answer[i][k]로 갱신한다.
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> answer[i][i]를 -로 갱신한다.
  -> answer[i][1:]을 언팩킹하여 출력한다.

Code

import sys
n, m=map(int, input().split())
INF=sys.maxsize
graph=[[INF]*(n+1) for _ in range(n+1)]
answer=[[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    a, b, c=map(int, input().split())
    graph[a][b]=min(graph[a][b], c)
    graph[b][a]=min(graph[a][b], c)
    answer[a][b]=b
    answer[b][a]=a
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if graph[i][j]>graph[i][k]+graph[k][j]:
                graph[i][j]=graph[i][k]+graph[k][j]
                answer[i][j]=answer[i][k]
for i in range(1, n+1):
    answer[i][i]='-'
    print(*answer[i][1:])