[백준] 1916번 : 최소비용 구하기

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

1916번: 최소비용 구하기

위의 문제는 데이크스트라 알고리즘인 최단경로 알고리즘 문제를 풀고 오면 똑같은 방식으로 문제를 해결 할 수 있다.

우선순위큐로 가장 짧은 거리인 노드부터 방문하고, 방문하려는 거리가 이미 더 짧은 거리라면 탐색을 멈춘다.

 

https://bigkwangs.tistory.com/23

[백준] 1753번 : 최단경로

위의 문제를 먼저 보고 오면 문제를 쉽게 이해 할 수 있다.

import heapq
INF = int(10e9)
N = int(input()) # 도시의 개수 ( 정점의 개수 )
M = int(input()) # 버스의 개수 ( 간선의 개수 )
graph = [[] for _ in range(N+1)]
for _ in range(M):
    start, end , cost = map(int, input().split())
    graph[start].append([end, cost]) # 끝, 비용
    
start , end = map(int, input().split())

distance = [INF for _ in range(N+1)]
queue = []
distance[start] = 0
heapq.heappush(queue, [distance[start], start])

while queue:
    cost, city = heapq.heappop(queue)
    if distance[city] > cost:
        continue
    
    for city2, cost2 in graph[city]:
        if distance[city2] > cost2 + cost:
            distance[city2] = cost2 + cost
            heapq.heappush(queue, [distance[city2], city2])
            
print(distance[end])