[테스트케이스 추가] 백준 1916 최소비용 구하기 (python, 파이썬)

1. 문제

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

1916번: 최소비용 구하기

 

 

 

2. 풀이

다익스트라!

 

 

 

3. 구현

import sys
import heapq
import math

# sys.stdin=open("input.txt")

N = int(sys.stdin.readline())
bus = int(sys.stdin.readline())

gph=[[] for _ in range(N+2)]
dist=[math.inf for _ in range(N+2)]
edges=[]

while bus:
  bus-=1
  a,b,c = map(int, sys.stdin.readline().split())
  gph[a].append((b,c))

v1,v2 = map(int, sys.stdin.readline().split())

dist[v1]=0
heapq.heappush(edges,(dist[v1],v1))
while edges:
  cost,pos = heapq.heappop(edges)
  for p,c in gph[pos]:
    c+=cost
    if dist[p]>c:
      dist[p]=c
      heapq.heappush(edges,(c,p))
print(dist[v2])

 

 

4. 추가 테스트케이스

8
20
7 1 1 
8 4 6 
7 5 2 
7 8 7 
3 8 5 
5 1 7 
5 2 1 
1 5 8 
5 8 1 
1 6 3 
4 2 6 
2 5 8 
2 6 1 
5 7 8 
7 3 9 
6 3 3 
6 2 8 
4 5 6 
2 8 2 
6 8 8 
2 7

답 16

9
24
9 1 4 
8 5 4 
1 5 1 
9 2 2 
7 8 5 
9 7 7 
7 6 3 
5 4 7 
5 1 3 
5 8 5 
5 2 1 
4 8 3 
5 7 7 
4 3 1 
6 5 5 
8 2 2 
4 6 5 
1 9 4 
9 6 9 
6 1 6 
5 6 5 
4 7 2 
3 2 2 
8 3 4 
1 7

답 8