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

PS/백준

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

지기_ 2021. 7. 5. 18:57

1. 문제

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

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

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. 추가 테스트케이스

답 16

답 8