[BAEKJOON]1916 최소비용 구하기 - Python

문제 요약

• 알고리즘 분류: 다익스트라
• 난이도: Gold5
• 문제내용:
  • 시작점 부터 도착점까지의 최단거리를 구해라

• 사이트: https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

문제풀이

   이번에는 문제 유형은 그래프 탐색중에 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘 기본적인것을 묻기 때문에 자세한 설명은 여기서 참조하면된다. 풀이에 대한 설명은 다익스트라 알고리즘알면 풀수 있기때문에 따로 설명은 하지 않겠다.

Code

Python

import sys
import heapq
from collections import deque

input = sys.stdin.readline
INF = float('inf')

def dijkstra(start, end):
    distances = [INF] * (N + 1)
    distances[start] = 0
    queue = [(start, 0)]
    while queue:
        now_node, now_distance = heapq.heappop(queue)
        if now_distance > distances[now_node]: continue

        for node, weight in grape[now_node]:
            distance = now_distance + weight
            if distance < distances[node]:
                distances[node] = distance
                heapq.heappush(queue, (node, distance))
    return distances[end]
        

N = int(input())
grape = {i:[] for i in range(1, N + 1)}
for _ in range(int(input())):
    a, b , value = map(int, input().split())
    grape[a].append((b, value))

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