BOJ - 11780 - 플로이드 2

import sys
_INF = 1e9

def findVertex(x, y, Floyd, visit, dist):
    if visit[x][y] == -1:
        dist.append(x)
        if x != y:
            dist.append(y)
    else:
        z = visit[x][y]
        findVertex(x, z, Floyd, visit, dist)
        dist.pop()
        findVertex(z, y, Floyd, visit, dist)

def solution():
    N = int(input())
    M = int(input())
    Floyd = [[_INF for _ in range(N + 1)] for _ in range(N + 1)]
    visit = [[-1 for _ in range(N + 1)] for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        if Floyd[a][b] > c:
            Floyd[a][b] = c

    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 Floyd[i][j] > (Floyd[i][k] + Floyd[k][j]):
                    visit[i][j] = k
                    Floyd[i][j] = (Floyd[i][k] + Floyd[k][j])

    for i in range(1, N+1):
        for j in range(1, N+1):
            print(Floyd[i][j] if Floyd[i][j] != 1e9 else 0, end=' ')
        print()
    
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            if (i == j):
                print(0)
                continue
            dist = []
            findVertex(i, j, Floyd, visit, dist)

            if Floyd[dist[0]][dist[-1]] == 1e9:
                print(0)
            else:
                print(len(dist), *dist)
    
solution()

https://www.acmicpc.net/problem/11780