티스토리 뷰

코딩/파이썬 백준

백준 1446 지름길 (파이썬)

박상어 2022. 2. 11. 15:24
728x90

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

 

1446번: 지름길

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이

www.acmicpc.net

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 w + distance[i] < distance[e]:
            distance[e] = w + distance[i]
print(distance[D])
 cs

 

 

'코딩 > 파이썬 백준' 카테고리의 다른 글

백준 16396 선 그리기 (파이썬)  (0) 2022.03.01
백준 7571 점 모으기 (파이썬)  (0) 2022.02.17
백준 2178 미로 탐색 (파이썬)  (0) 2022.02.10
백준 5545 최고의 피자 (파이썬)  (0) 2022.02.09
백준 12018 Yonsei TOTO (파이썬)  (0) 2022.02.09
댓글