[BaekJoon] 백준 1446번 : 지름길

1446번 : 지름길

출발점(0번 노드) 에서 도착점(D번 노드) 까지의 최소 거리를 구하는 문제이기 때문에 다익스트라를 사용하면 된다.

기본적으로 i번 노드, i + 1번 노드를 출발노드와 도착노드로 하는 거리가 1인 길로 이어준다.

그리고 문제에서 주어지는 지름길 정보를 입력받는다.

그런데 지름길로 가는 경우 거리가 더 먼 입력값을 주는 경우도 있고 목표 거리보다 멀리 있는 점을 도착점으로 주는 경우도 있다.

이런 예외 상황을 잘 걸러서 지름길 정보까지 추가했으면 다익스트라를 수행하면 된다.

---

import heapq


def solution(graph):
    for _ in range(N):
        start, end, dist = map(int, input().split())
        # 지름길인데 거리가 더 먼 경우, 출발점이나 도착점이 D 보다 큰 경우 필요 없음.
        if end - start < dist or start > D or end > D:
            continue
        else:
            graph[start].append([end, dist])

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

    distance = [float('inf')] * (D + 1)
    queue = []
    heapq.heappush(queue, [0, 0])
    while queue:
        now, dist = heapq.heappop(queue)
        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(queue, [i[0], cost])

    return distance[D]


if __name__ == "__main__":
    N, D = map(int, input().split())
    graph = {i: [] for i in range(D + 1)}

    print(solution(graph))