[알고리즘][Python] 백준(BOJ) 1916 최소비용 구하기_파이썬

 

1916 최소비용 구하기    www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

 

 

 

 

문제 풀기 전 공부할 것 : 다익스트라

 

 

 

 

 

 

 

풀이 1

<내용>

• 우선순위 큐를 이용해서 다익스트라로 문제를 해결한다.

 

 

<코드>

import heapq
import sys
input = sys.stdin.readline

INF = 999999999
n = int(input())
m = int(input())
bus = [[] for _ in range(n)]
for _ in range(m):
    a, b, w = map(int, input().split())
    bus[a-1].append((b-1, w))
    
a, b = map(int, input().split())
que = []
distance = [INF for _ in range(n)]
distance[a-1] = 0
heapq.heappush(que, (distance[a-1], a-1))
while que:
    curr_dist, curr_node = heapq.heappop(que)
    
    if distance[curr_node] < curr_dist:
        continue
        
    for adj, w in bus[curr_node]:
        dist = curr_dist + w
        if dist < distance[adj]:
            distance[adj] = dist
            heapq.heappush(que, (dist, adj))
            
print(distance[b-1])

 

 

 

 

 

 

 

 

 

풀이 2

<코드>

import heapq
import sys
input = sys.stdin.readline

INF = 999999999
n = int(input())
m = int(input())
bus = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    bus[a-1].append((b-1, c))
    
a, b = map(int, input().split())

que = []
heapq.heappush(que, (0, a-1))
check = [INF for _ in range(n)]
check[a-1] = 0
while que:
    count, city = heapq.heappop(que)   
    if city == b-1:
        break
    for c, cnt in bus[city]:
        if count+cnt < check[c]:
            check[c] = count+cnt
            heapq.heappush(que, (count+cnt, c))
            
print(check[b-1])