[파이썬] 백준 1916 : 최소비용 구하기 (골드5)

[파이썬] 백준 1916 : 최소비용 구하기 (골드5)

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

---

풀이

방향성 생각

• 전형적인 다익 기본
  • A -> B로가는 최소 거리

---

전체코드

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')]*(N+1)
V[start] = 0
heap = [(0,start)]
while heap:
    t, x = hq.heappop(heap)

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

print(V[end])

코멘트

• 기본문제