[파이썬] [DP] 백준 1446 지름길

문제

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

1446번: 지름길

코드

import sys
input=sys.stdin.readline

n,d=map(int, input().split())

graph=[[] for _ in range(d+1)]
for _ in range(n):
    a,b,c=map(int, input().split())
    if b<=d:
        graph[a].append([b,c])
dp=[]
for i in range(d+1):
    dp.append(i)

for i in range(d+1):
    # 지름길(dp[i])과 고속도로(dp[i-1]+1) 비교
    dp[i] = min(dp[i], dp[i - 1] + 1)
    if graph[i]:
        for des,dis in graph[i]:
            #지름길이 더 짧을 경우 갱신
            dp[des]=min(dp[des], dis+dp[i])

print(dp[d])

시간 복잡도

O(고속도로 길이)