[백준/Python] 1446번 : 지름길

문제

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

---

풀이

다익스트라로 구현하였다.
0에서 시작하여 d까지 가야 하므로 거리를 모두 노드로 볼 수 있다.
for문을 통해 graph를 최소거리가 1로 초기화하고, 최단 거리 테이블을 무한으로 초기화한다.
입력받은 지름길을 graph에 추가한다. (만약 종료지점이 d보다 크다면 추가하지 않는다.)

다익스트라 함수 구현
- 시작 노드로 가기 위한 최단 경로를 0으로 설정하여 큐에 삽입한다.
- q가 존재한다면, 가장 최단 거리가 짧은 노드에 대한 정보를 heappop 한다. (dist, now)
- dist가 now까지의 최단 거리보다 길다면, continue 한다.
- dist가 더 짧다면, 현재 노드의 지름길들을 반복문으로 탐색한다.
- dist에 지름길의 길이를 더한 값이 지름길 끝지점의 최단 거리보다 짧다면, 해당 값을 갱신하고 q에 heappush 한다.

---

코드

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

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 i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost, i[0]))


n , d = map(int, input().split())
graph = [[] for _ in range(d+1)]
distance = [INF] * (d+1)

for i in range(d):
    graph[i].append((i+1, 1))

for _ in range(n):
    s, e, l = map(int, input().split())
    if e > d :
        continue
    graph[s].append((e,l))

dijkstra(0)
print(distance[d])