알고리즘 스터디 - 백준 1916번 : 최소비용 구하기

문제 해석

A에서 B로 가는데 드는 최소 비용을 출력하기

• N개의 도시와 M개의 버스가 존재한다.

입력

1. 도시의 개수 N
2. 버스의 개수 M
3. start, end, weight 가 주어짐
4. 우리가 구하고자 하는 출발점과 도착점의 도시번호가 주어짐

-> BFS나 DFS, 다익스트라 셋중 하나 써도 될 것 같다.

알고리즘 코드

import sys, heapq
input = sys.stdin.readline
INF = sys.maxsize

N = int(input())
M = int(input())

path = {i: [] for i in range(1, N+1)}
dist = {i: INF for i in range(1, N+1)}

for _ in range(M):
    start, end, weight = map(int, input().split())
    path[start].append((weight, end))

def dijkstra(start):
    dist[start] = 0

    queue = []
    heapq.heappush(queue, [dist[start], start])

    while queue:
        current_distance, current_destination = heapq.heappop(queue)
        
        if dist[current_destination] < current_distance:
            continue
        
        for new_distance, new_destination in path[current_destination]:
            distance = dist[current_destination] + new_distance
            if distance < dist[new_destination]:
                dist[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])

start, end = map(int, input().split())

dijkstra(start)

print(dist[end])