[BOJ][Python][골5][1916] 최소비용 구하기

문제 링크

문제링크

풀이

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
from operator import itemgetter
from collections import Counter, deque
from copy import deepcopy
import heapq

# sys.stdin = open("input.txt", "r")
####################
#      CONST
####################
INF = int(1e9)

####################
#      INPUT
####################
n = int(input())
m = int(input())

graph = [[] for i in range(n + 1)]  # 그래프
visited = [False] * (n + 1)  # 방문 여부
dist = [INF] * (n + 1)  # 시작노드부터 각 노드까지 최단 거리

for _ in range(m):
    a, b, c = map(int, input().split())
    # 노드 a에서 b로 가는 비용이 c
    graph[a].append([b, c])

start, end = map(int, input().split()) # 시작노드, 도착노드

####################
#      SOLVE
####################


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # (x까지의 비용 = 0, x)
    dist[start] = 0
    while q:
        x_weight, x = heapq.heappop(q) #
        if dist[x] < x_weight:
            continue
        for nx, nx_weight in graph[x]: # x에서 nx까지 가는 비용 = nx_weight
            cost = x_weight + nx_weight # 현재까지의 비용 + 다음 노드까지의 비용
            if cost < dist[nx]:
                dist[nx] = cost
                heapq.heappush(q, (cost, nx))


dijkstra(start)

####################
#      ANSWER
####################
print(dist[end])

####################
#      SYS
####################
# if __name__ == "__main__":
#     main()

Success Notice: 수고하셨습니다.