[Baekjoon] Shortest Path - 1446 지름길

문제

1446번: 지름길

 

풀이

기본적인 dijkstra 골격에 추가적인 부분을 신경써주면 된다.

 

1. 모든 길은 연결되어있다. (모든 정점은 길이가 1인 단방향 간선으로 연결되어 있다.)

2. 지름길의 길이가 주어질 때, 내가 가야할 길이보다 큰 값으로 주어질 수 있다. (list out of index range Error)

 

import sys
import heapq

INF = 1e9

n, d = map(int, sys.stdin.readline().rstrip().split())

# 지름길의 길이가 진행해야할 길이보다 클 수 있어 10,000로 선언한다.
distance = [INF] * (10000 + 1)
graph = [[] for _ in range(10000 + 1)]

# 모든 길은 연결되어 있다.
for i in range(10000):
    graph[i].append((i + 1, 1))

for _ in range(n):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append((b, c))


def dijkstra(distance, start, d):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for v in graph[now]:
            cost = dist + v[1]
            if distance[v[0]] > cost:
                distance[v[0]] = cost
                heapq.heappush(q, (cost, v[0]))

    return distance[d]


print(dijkstra(distance, 0, d))

 

채점 결과