악곱 == 악성곱슬

DP

---

이 문제는 0부터 시작해서 D 까지의 최단 경로를 구하는 문제이다. 지름길이 없을 경우 최단 경로는 그대로 D가 된다. N개의 지름길이 주어지고 이는 0~D사이의 임의의 두 점과 지름길의 길이가 주어진다.

역주행은 불가능 하다.

그래서 우선 내가 생각한 방법은 0~D까지의 1차원 배열을 선언 후 DP를 사용하는 것이다. 배낭문제와 유사하게 도착위치에서 지름길이 있다면 해당 지름길을 경유 하는 경우 vs 그냥 고속도로를 달리는 경우 의 최소값을 계속 업데이트 하는 방식으로 구현하면 된다.

구현

---

import sys

def dp(d):
    shortcuts.sort(key=lambda x: x[1])
    dist = [INF] * (d+1)
    dist[0] = 0
    idx = 0
    for i in range(1, d+1):
        while idx < len(shortcuts) and shortcuts[idx][1] == i:
            dist[i] = min(dist[i], i, dist[shortcuts[idx][0]] + shortcuts[idx][2])
            idx += 1
        dist[i] = min(dist[i], dist[i-1] + 1, i)
    return dist[-1]

if __name__ == "__main__":
    N, D = map(int, sys.stdin.readline().rstrip().split())
    shortcuts = []
    INF = int(1e9)
    for _ in range(N):
        shortcuts.append(list(map(int, sys.stdin.readline().split())))
    print(dp(D))