[BOJ] 1446. 지름길 (🥈, 다익스트라)

🔗

풀이

최단거리를 구할 수 있으며 도중에 지름길이 존재한다. 항상 +1 칸을 할 수 있고, 지름길이 있으면 지름길로 이동한다. 각 위치에 대해 해당 위치에 도달할 수 있는 최대 거리는 해당 위치의 값이 된다. 만약 5km 위치에 있다면 지름길 없이 도달하는데는 5km 이상이 걸릴 수 없다.

역주행이 되지 않는다는 문제의 조건을 못 보고 지름길을 양방향 설정했다가 시간초과 날 뻔

# 지름길

import heapq
from collections import defaultdict

def dijkstra(start):
    Q = [(0, start)]
    dist = [i for i in range(D+1)]
    while Q:
        w, now = heapq.heappop(Q)

        if now > D or w > dist[now]:
            continue
        dist[now] = w
        for next, next_w in node[now]:
            heapq.heappush(Q, (w + next_w, next))
        heapq.heappush(Q, (w + 1, now + 1))
            
    return dist[-1]

N, D = map(int, input().split())
node = defaultdict(list)

for _ in range(N):
    s, e, d = map(int, input().split())
    node[s].append((e, d))
print(dijkstra(0))