[BOJ] 1916. 최소비용 구하기

 

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

문제: 목표 도시로 이동하는 최소비용을 구하여라.

 

문제 이해하기!!

최소 비용 그래프문제라면 제일 먼저 생각해봐야 할 것!

바로 다익스트라입니다. 이 문제도 다익스트라인데요.

그래프 연결은 상호적 연결이 아니기 때문에 한 쪽만 연결해 줍니다.

그리고 다익스트라로 비용 구하시면 됩니다.

---

문제 풀어보기!!

일단 문제를 보면 M이 10만까지 가능하기 때문에 input을 stdin.readline으로 바꿔줍니다.

입력받는 그래프를 딕셔너리로 바꿔주고, 다익스트라에 필요한 dp 배열 하나와 HeapQ를 만들어줍니다.

Q에 처음 시작 도시를 넣고, 시작도시로 가는 비용은 0입니다. -> (0, s)

그리고 다익스트라 알고리즘을 돌리면 끝!!

• 간단한 설명
  • 다익스트라 알고리즘 - dp와 bfs를 합친 알고리즘
  • Heap - 트리형식으로 최소나 최대 값을 먼저 pop하는 자료구조

Heap과 다익스트라를 모르시면 먼저 공부하시고 푸는 것을 추천드립니다.

 

코드:

import heapq
from collections import defaultdict
from sys import stdin
input = stdin.readline


N = int(input())
M = int(input())
dic = defaultdict(list)
for _ in range(M):
    a, b, c =map(int, input().split())
    dic[a].append((c,b))

s, e = map(int, input().split())
Q = [(0,s)]
dp = [float('inf')] * (N+1)
dp[s] = 0
while Q:
    tmp = heapq.heappop(Q)
    for i in dic[tmp[1]]:
        if dp[i[1]] > dp[tmp[1]] + i[0]:
            dp[i[1]] = dp[tmp[1]] + i[0]
            heapq.heappush(Q, i)

print(dp[e])