백준 1446 : 지름길 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline
INF=float('inf')

def Dijkstra():

    heap=[] ; heapq.heappush(heap, (0,0) )
    dp[0]=0
    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:

            next_value+=value
            if next_value<dp[next_node]:
                dp[next_node]=next_value
                heapq.heappush(heap , (next_value , next_node))

N,D=map(int,input().split())

dp=[INF]*(100000)
graph=[ [] for _ in range(D+2) ]
for i in range(D+1):
    graph[i].append((1,i+1)) #다음방향으로 이동하기 위해서 i+1 을 넣어야한다.
for i in range(N):
    A,B,C=map(int,input().split())
    if B>D:
        continue
    graph[A].append((C,B))# 단방향.

Dijkstra()

print(dp[D])

📌 어떻게 접근할 것인가?

다익스트라를 통해 풀었습니다.

일단 예제부터 보겠습니다.

• 5 150
  0 50 10
  0 50 20
  50 100 10
  100 151 10
  110 140 90

목표는 0 지점에서 150 지점으로 가는것입니다.

이때 한 칸 이동할때마다 거리가 1씩증가합니다. 다만 지름길을 통해 간다면

0-50-100 으로 10+10 의 가중치가 발생하고 총 20 의 가중치가 필요합니다.

그리고 100-150 까지 가는데 거리가 50 이므로 20+50=70 입니다.

100-151 로 갈 수 없는 이유는 역방향으로 길을 갈 수 없기 때문입니다.

따라서 graph 에 모든 가중치를 1 로 설정해주고 다음방향으로 이동할 수 있도록 인덱스를 i+1 을 넣어줍니다.

이후 다익스트라를 통해 최단경로를 구한 후 dp[D] 를 출력합니다.