백준 1446. 지름길

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

import sys, heapq

n, d = map(int, sys.stdin.readline().split())  # n: 지름길 개수, d: 고속도로 길이

# 그래프 초기화: d+1 길이의 빈 리스트 생성
graph = [[] for _ in range(d+1)]
dist = [float("inf")] * (d+1)  # 0부터 d까지 모든 지점의 최단 거리

# 기본적으로 1칸씩 이동하는 경우 추가
for i in range(d):
    graph[i].append((i+1, 1))  # i에서 i+1로 가는 거리는 항상 1

for _ in range(n):
    start, end, length = map(int, sys.stdin.readline().split())  # 시작점, 끝점, 지름길 길이
    if end <= d:  # 지름길의 끝점이 고속도로 길이를 넘어가지 않을 경우만 추가
        graph[start].append((end, length))

q = []
heapq.heappush(q, (0, 0))  # 시작점 (거리 0, 위치 0) 추가
dist[0] = 0  # 시작점의 최단 거리 초기화

while q:
    w1, now = heapq.heappop(q)  # 현재 노드와 그 거리(w1)를 꺼냄

    for nxt, w2 in graph[now]:  # 현재 노드 now와 연결된 노드 nxt와 그 거리 w2를 확인
        cost = dist[now] + w2  # 현재 노드를 거쳐 nxt로 가는 거리 계산
        if dist[nxt] > cost:  # 더 짧은 경로가 발견되면 업데이트
            dist[nxt] = cost
            heapq.heappush(q, (cost, nxt))  # 갱신된 거리와 노드를 큐에 추가

print(dist[d])