https://www.acmicpc.net/problem/1916
import sys
import heapq
input = sys.stdin.readline
city = int(input())
bus = int(input())
graph = [[] for _ in range(city+1)]
distance = [int(1e9)]*(city+1)
for _ in range(bus):
u, v, w = map(int, input().split())
graph[u].append((v, w))
start, end = map(int, input().split())
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, node = heapq.heappop(q)
if distance[node] < dist:
continue
for next in graph[node]:
cost = distance[node] + next[1]
if cost < distance[next[0]]:
distance[next[0]] = cost
heapq.heappush(q, (cost, next[0]))
dijkstra(start)
print(distance[end])
다익스트라 알고리즘을 이용하여 풀면 된다.
답안 출력시 distance[end]를 출력하면 된다.