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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
import heapq

input = sys.stdin.readline
# 도시의 개수 n
n = int(input())
# 버스의 개수 m
m = int(input())
# 버스 정보
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((c, b)) #(비용, 도착지)
# 최소 거리 테이블
INF = int(1e9)
distance = [INF]*(n+1)
# 출발점, 도착점
start, end = map(int, input().split())

# 다익스트라
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            continue
        # 인접 경로 탐색
        for x in graph[now]:
            cost = dist + x[0]
            if cost < distance[x[1]]:
                distance[x[1]] = cost
                heapq.heappush(q, (cost, x[1]))

dijkstra(start)
print(distance[end])

---

🧂아이디어

• heapq로 구현한 Priority queue를 사용해서 풀 수 있었던 dijkstra 문제.
• 거의 기본 문제나 마찬가지