최소비용 구하기

백준 1916

A번째 도시에서 B번째 도시까지 가는데 드는 최소비용 구하기.

• N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.
• 도시의 번호는 1부터 N까지이다.
• 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다.
• 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
• 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

입출력

입력	출력
5 8 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 1 5	4

---

접근 방식

: 출발점에서 갈 수 있는 다른 노드들의 최소비용을 구하고 도착점의 값을 구한다.
-> 다익스트라 알고리즘 이용.

알게된 점

if dp[n] < w:
    continue

이 코드를 쓰지 않아도 답은 잘 나온다. 그런데 계속 시간 초과가 나서 정답이었던 코드와 비교해보니 이 부분이 없었다. 이 코드는 dp[n]이 현재 n에 해당하는 가중치 w보다 작다면 이미 이전에 탐색하였다는 뜻이므로 continue를 통해 아래의 코드를 실행하지 않고 넘어갈 수 있다. 이전까지 중요하게 생각하지 않았는데 앞으로는 꼭 넣어주어야겠다!

코드

import heapq
import sys

def dks(bus, dp, s, e):
    dp[s] = 0
    q = []
    heapq.heappush(q, (0, s)) #가중치, 노드

    while q:
        w, n = heapq.heappop(q)

        if dp[n] < w:
            continue
            
        for ad_n, ad_w in bus[n]:
            new_w = w + ad_w
            if new_w < dp[ad_n]:
                dp[ad_n] = new_w
                heapq.heappush(q, (new_w, ad_n))

    return dp[e]


n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
bus = [[] for _ in range(n+1)]

for _ in range(m):
    s, e, w = map(int, sys.stdin.readline().split())
    bus[s].append((e, w))
s, e = map(int, sys.stdin.readline().split())

dp = [1e9]*(n+1)
print(dks(bus, dp, s, e))