백준 11780 - 플로이드 2 (파이썬)

Answer

import sys

input = sys.stdin.readline
INF = float('inf')

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

dp = [[INF] * (n + 1) for _ in range(n + 1)]
path = [[0] * (n + 1) for _ in range(n + 1)]

def find_path(i, j):
    if path[i][j] == 0:
        return []

    k = path[i][j]
    return find_path(i, k) + [k] + find_path(k, j)

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

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

def floyd_warshall():
    for k in range(n + 1):
        for i in range(n + 1):
            for j in range(n + 1):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
                    path[i][j] = k
                
floyd_warshall()

for i in range(1, n + 1):
    for j in range(1, n + 1):
        print(dp[i][j] if dp[i][j] != INF else 0, end = ' ')
    print()

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if dp[i][j] in (0, INF):
            print(0)
        else:
            tmp = [i] + find_path(i, j) + [j]
            print(len(tmp), end = ' ')
            print(*tmp)