BOJ 1916 최소비용 구하기

문제

접근 방법

시작점에서 끝점까지의 최단 거리를 구하는 문제이고 양의 weight만 있으므로 dijkstra를 사용하면 된다고 판단했다.

정답 코드

import sys
import heapq
input = sys.stdin.readline

'''
시작점에서 끝점까지의 최소거리를 구하면 되므로 dijkstra로 풀면 된다.
'''
inf = int(1e9)
n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]

for _ in range(m):
  s,e,cost = map(int, input().split())
  graph[s].append((e,cost))

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

q = []
heapq.heappush(q, [0,start])
distances = [inf]*(n+1)
distances[start] = 0

while q:
  mid_cost, mid_node = heapq.heappop(q)
  if distances[mid_node] < mid_cost:
    continue
  for end_node, end_cost in graph[mid_node]:
    new_distance = end_cost + mid_cost
    if new_distance < distances[end_node]:
      distances[end_node] = new_distance
      heapq.heappush(q, [new_distance, end_node])

print(distances[target])