다익스트라 알고리즘을 연습하기 위해 이 문제를 풀어보았다. 처음으로 다익스트라 알고리즘을 활용해봤기 때문에 많이 미숙하여 코드를 찾아보며 풀이하였다.

우선 그래프를 인접 리스트 형식으로 저장하였다. 이때 지름길의 종료 위치가 도착지보다 멀리 있을 경우에는 그래프에 저장하지 않았다. 그리고 거리를 저장하는 리스트를 만들고 최대값으로 채운 뒤에 인덱스 0의 값을 0으로 갱신해주었다. BFS에 사용할 큐를 최소힙으로 선언하고 while문 안에서 각 지름길에 대한 그래프를 순회하며 그 중 더 작은 값을 더해주며 반복하였다. 반복문을 탈출하면 거리를 저장한 리스트의 인덱스 d를 출력한다.

거리를 저장한 리스트를 출력해보니 다음과 같이 출력되었다.

[0, 1, 2, 3, 4, 5, ... , 46, 47, 48, 49, '10', 11, 12, 13, 14, 15, 16, 17, 18, ... , 57, 58, 59, '20', 21, 22, ...  65, 66, 67, 68, 69, '70']

거리를 저장한 리스트를 이전의 거리보다 1씩 증가시키고 만약 지름길이 있는 위치일 경우에는 지름길 중 가장 짧은 길이를 택하여 거리를 그 지름길의 길이로 갱신해주고 다시 1씩 증가시키는 방식인 것을 확인할 수 있다.

• n, d를 입력받는다.
• graph를 2차원 리스트로 선언한다.
• d번 반복하는 i에 대한 for문을 돌린다.
  -> graph[i]에 (i+1, 1)을 넣는다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> 지름길에 대한 정보를 start, end, length로 받는다.
  -> 만약 end가 d보다 클 경우에는 다음으로 넘긴다.
  -> graph[start]에 (end, length)를 넣는다.
• 최대값을 INF에 저장한다.
• 거리를 저장할 리스트 distance를 INF d+1개로 채운다.
• distance[0]을 0으로 갱신한다.
• BFS에 사용할 큐 q를 최소힙으로 선언한다.
• q에 (0, 0)을 넣는다.
• q가 있을 동안 반복하는 while문을 돌린다.
  -> dst, cur을 q에서 추출한다.
  -> 만약 distance[cur]이 dst보다 작을 경우에는 다음으로 넘긴다.
  -> graph[cur]을 end, length에 대하여 순회하는 for문을 돌린다.
  --> cost에 dst+length를 저장한다.
  --> 만약 distance[end]가 cost보다 크다면,
  ---> distance[end]를 cost로 갱신한다.
  ---> q에 (cost, end)를 저장한다.
• distance[d]를 출력한다.

Code

import sys
import heapq
n, d = map(int, input().split())
graph = [[] for _ in range(d+1)]
for i in range(d):
    graph[i].append((i+1, 1))
for i in range(n):
    start, end, length = map(int, input().split())
    if end > d: continue
    graph[start].append((end, length))

INF = sys.maxsize
distance = [INF]*(d+1)
distance[0] = 0

q = []
heapq.heappush(q, (0, 0))
while q:
    dst, cur = heapq.heappop(q)
    if distance[cur] < dst: continue
    for end, length in graph[cur]:
        cost = dst + length
        if distance[end] > cost:
            distance[end] = cost
            heapq.heappush(q, (cost, end))
print(distance[d])