11779 최소비용 구하기 2 python

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

11779번: 최소비용 구하기 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

다익스트라 알고리즘

최소비용 구하기 1916번 문제에서 경로까지 추가해서 출력해야 한다.

경로를 추가하기위해서 경로 변수를 추가해서 각 지점까지 오기위한 바로 전단계 위치를 저장해두면서 풀었다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import heapq
import sys
input = sys.stdin.readline

"""
다익스트라

visited에 경로까지 추가함.
"""

n = int(input())
m = int(input())
graph = [[] for i in range(n+1)]
INF = float('inf')

for i in range(m):
    start, end, weight = map(int,input().split())
    graph[start].append((weight, end))
startPoint, endPoint = map(int,input().split())

def dijkstra(sp, ep):
    dp = [INF] * (n+1)
    dp[sp] = 0
    route = [0] * (n+1)
    route[sp] = sp
    heap = [(0, sp)]
  
    while heap:
        w1, s = heapq.heappop(heap)

        if dp[s] < w1:
            continue
        
        for w2, e in graph[s]:
            if dp[e] > w1 + w2:
                dp[e] = w1 + w2
                route[e] = s
                heapq.heappush(heap, (w1 + w2, e))

    return dp[ep], route

cost, routes = dijkstra(startPoint, endPoint)
print(cost)
ans = [endPoint]
x = endPoint
while True:
    x = routes[x]
    ans.append(x)
    if x == startPoint:
        break
ans.reverse()
if n==1:
    print(1)
    print(1)
else:
    print(len(ans))
    print(*ans)