Coding Test/문제 풀이
[문제 풀이] 백준 1446
EUNJI HA
2022. 3. 25. 16:15
1446번: 지름길
첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이
www.acmicpc.net
해결 과정
다익스트라 알고리즘을 활용한 것이 뭐가 있을까 하다가 발견한 문제.
이것 역시 다른 코드를 참고하며 이해했다.
나의 풀이
import sys
N, D = map(int, sys.stdin.readline().split())
graph = []
for i in range(N):
start, end, shortcut = map(int, input().split())
if end <= D: graph.append((start, end, shortcut)) # 거리 넘어가는 건 제외
dis = [i for i in range(D+1)] # [0, 1, 2, 3, ... D]
for i in range(D+1):
dis[i] = min(dis[i], dis[i-1] + 1)
for start, end, shortcut in graph: # 지름길 돌면서 업데이트하기
if start == i:
dis[end] = min(dis[start] + shortcut, dis[end])
print(dis[D])
다른 풀이
IDEA