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

🥚문제

---

🥚입력/출력

---

🍳코드

import heapq
import sys

input = sys.stdin.readline
# v:정점의 개수, e: 간선의 개수
v, e = map(int, input().split())
# k: 시작 정점의 번호
k = int(input())
# 그래프 선언
graph = [[] for _ in range(v+1)]
# 각 간선 정보 입력
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((c, b)) # (가중치, 도착 노드)
# 최단거리 테이블
INF = sys.maxsize
distance = [INF]*(v+1)

# dijkstra
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # (가중치, 노드) 순!!!
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        # 이미 탐색한 정점은 스킵
        if distance[now] < dist:
            continue
        # 인접 경로 탐색
        for i in graph[now]:
            cost = dist + i[0]
            if cost < distance[i[1]]:
                distance[i[1]] = cost
                heapq.heappush(q, (cost, i[1]))

dijkstra(k)
for i in range(1, v+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

---

🧂아이디어

• heapq로 구현한 Priority queue를 사용해서 풀 수 있었던 dijkstra 문제.

• 초반 두 시도에서 시간초과가 났던 이유:
  우선순위 큐에 (가중치, 노드) 순서로 넣어야 가중치를 기반으로 가장 짧은 경로를 고를 수 있는데 아무 생각 없이 (노드, 가중치) 순서로 넣어 버렸다.