1916-백준-최소비용 구하기

1. 문제 출처

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

1916번: 최소비용 구하기

2. 풀이

단순 데이크스트라 알고리즘을 이용하는 문제이다.

import sys
input = sys.stdin.readline

import heapq

# 최대값 정의
INF = float('inf')
# 입력
n = int(input())
m = int(input())
# 그래프와 거리 초기화
graph = [[] for _ in range(n+1)]
distance = [INF] *(n+1)

# 그래프 입력값으로 초기화
for idx in range(m):
    a,b,c = map(int,input().split())
    # a -> b 도시로 가는 데 팔요한 비용 c
    graph[a].append([b,c])
    
#입력 받기
start , end = map(int,input().split()) 


#데이크스트라 알고리즘
def dik(start):
    # heap자료구조를 사용하여 우선 순위 큐 구현
    q = []
    # 출발할 도시 큐에 넣기
    heapq.heappush(q,[0,start])
    # 시작 도시의 거리를 0으로
    distance[start] = 0
    # 큐가 빌때까지
    while q:
        # 큐에서 가장 가장 거리가 짧은 값 꺼내기
        weight, node = heapq.heappop(q)
        # 만약 이미 한 것이면 넘기기(안하면 시간 초과 뜸)
        if distance[node] < weight:
            continue
        # 인접한 노드 확인
        for n , w in graph[node]:
            cost = w+weight
            if distance[n] > cost:
                distance[n] = cost
                heapq.heappush(q,[cost,n])

                
dik(start)
# 결과값에서 end 까지의 거리 출력
print(distance[end])