# BOJ - 11780 - 플로이드 2

Updated:

``````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

Categories:

Updated: