[파이썬] 백준 11779 : 최소비용 구하기 2 (골드3)

[파이썬] 백준 11779 : 최소비용 구하기 2 (골드3)

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

---

풀이

방향성 생각

• 최소비용 구하기 1916 이랑 같은 문제.

• 다익스트라 + 역추적

• 기존 다익스트라 배열에 previous node를 기록해주는 리스트를 추가한다.

---

전체코드

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

N = int(input())
M = int(input())

G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))

start,end = map(int,input().split())

V = [[float('inf'),None]]*(N+1)
V[start] = [0,-1] 
heap = [(0,start)]
while heap:
    t,x = hq.heappop(heap)

    if t > V[x][0]:
        continue
    for nx, cost in G[x]:
        nt = t + cost
        if nt < V[nx][0]:
            V[nx] = [nt,x]
            hq.heappush(heap,(nt,nx))

path = [end]
while True:
    px = V[path[-1]][1]
    if px == -1:
        break
    else:
        path.append(px)
print(V[end][0])
print(len(path))
print(*path[::-1])

코멘트

• 기본 문제