최소비용 구하기
백준 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))
Author And Source
이 문제에 관하여(최소비용 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sezeom/최소비용-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)