[백준 11780번] 플로이드 2 (Python3)

import sys
input = sys.stdin.readline
INF = 10**9

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

graph = [[INF]*(N+1) for i in range(N+1)]
path = [[[i] for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  x,y,w = map(int,input().split())
  graph[x][y] = min(graph[x][y],w)

for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      if i == j:
        continue
      if graph[i][j] > graph[i][k]+graph[k][j]:
        graph[i][j] = graph[i][k]+graph[k][j]
        path[i][j] = path[i][k]+path[k][j]

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

for i in range(1,N+1):
  for j in range(1,N+1):
    if graph[i][j] == INF:
      print(0)
    else:
      print(len(path[i][j])+1,i,*path[i][j])

플로이드 워셜 알고리즘 기본문제에 경로추적을 더한 문제

 

path 배열을 만들어서 각 배열에 경로를 넣은 후, 경로가 갱신될때마다 그래프값을 더해주면서 경로도 같이 더해주면 된다.