티스토리 뷰

728x90

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

 

1916번: 최소비용 구하기

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

www.acmicpc.net

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import heapq
import sys
 
std = sys.stdin
= int(std.readline())
= int(std.readline())
inf = 10 ** 10
= [[] for _ in range(n + 1)]
dp = [inf for _ in range(n + 1)]
for i in range(m):
    a, b, w = map(int, std.readline().split())
    s[a].append([b, w])
start, end = map(int, std.readline().split())
 
 
def dijkstra(start):
    dp[start] = 0
    hq = []
    heapq.heappush(hq, [0, start])
    while hq:
        w, n = heapq.heappop(hq)
        if dp[n] < w:
            continue
        for n_n, wei in s[n]:
            n_w = w + wei
            if dp[n_n] > n_w:
                dp[n_n] = n_w
                heapq.heappush(hq, [n_w, n_n])
 
 
dijkstra(start)
print(dp[end])
cs

 

댓글