11700_플로이드2

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

11780번: 플로이드 2

 

 

해당 유형의 문제는 역시 다익스트라 알고리즘을 활용하고 최단거리 역추적을 이용하면 꽤나 쉽게 풀 수 있다.

 

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n= int(input())
m = int(input())
graph = [ [] for _ in range(n+1)]
for _ in range(m):
    s,e,v = map(int,input().split())
    graph[s].append((e,v))

dist = [ [INF] * (n+1) for _ in range(n+1)]
visited = [ [0] *(n+1) for _ in range(n+1)]

for i in range(1,n+1):

    q = [(0,i)]
    while q:
        cnt,node = heapq.heappop(q)

        if dist[i][node] < cnt:
            continue
        if node == i:
            dist[i][node] = 0

        for next,value in graph[node]:
            if dist[i][next] > cnt + value:
                dist[i][next] = cnt + value
                heapq.heappush(q,(cnt+value,next))
                visited[i][next] = node
for i in range(1,n+1):
    for j in range(1,n+1):
        print(dist[i][j] if dist[i][j] != INF else 0,end=' ')
    print()

for i in range(1,n+1):
    for j in range(1,n+1):
        result = [j]
        tmp = visited[i][j]
        while tmp != 0:
            result.append(tmp)
            tmp = visited[i][tmp]
        if len(result)==1:
            print(0)
        else:
            result.reverse()
            print(len(result),*result)

 

 

주의할 점은 만약 특정 도시에 어떤 버스도 가지 않는다면 INF값인 1000000000가 저장되기 때문에 이를 0으로 바꿔주어야 100%까지 가서 틀렸습니다를 마주하지 않을 수 있다. 이를 유의하도록 하자.