[백준 1446] 지름길 (python)

1446번: 지름길

---

다익스트라 알고리즘을 이용한다.

1. 지름길이 없을때 자기 자신을 default로 가지는 arr 배열을 생성한다.
2. 0부터 목적지까지 돈다.
3. 이전지점+1 이 더 작다면 update해준다.
4. 지름길이 있다면 저장된 길이 (distance[타겟점])와 뻗어나간 길이 (w + distance[시작점]) 중 작은 것으로 update해준다.

(지름길 시작지점이 D보다 작다고 해서 arr 배열을 range(D+1)로 했는데 Indexerror가 난다. 왜나는 걸까?)

import sys
input = sys.stdin.readline

N, D = map(int, input().split())
arr = [[] for _ in range(10001)]
for _ in range(N):
    s, e, w = map(int, input().split())
    arr[s].append([w, e])
distance = [i for i in range(D+1)]

for i in range(D+1):
    if i != 0:
        distance[i] = min(distance[i], distance[i-1]+1)
    for w, e in arr[i]:
        if e <= D and distance[e] > w + distance[i]:
            distance[e] = w + distance[i]

print(distance[D])