[백준] 1446번: 지름길

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

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

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

입출력 예제

풀이

다익스트라를 활용한 풀이.
vertex의 수는 최대 10001개 이고 최대 시간은 2초 이므로
O(NlogN) = 10001 * 15.xxx 로 충분하다

초기 그래프를 생성한다.
0~150 까지 일자로된 단뱡향성 그래프를 인접행렬도 만들고
지름길을 만들어준다.
만약 같은 길이 또 나올 경우 거리가 짧은 거리만 남겨둔다.

이후 다익스트라 알고리즘을 사용해서 각 경로까지 가는데
최소 경로를 구하고 M 까지 가는 거리의 최소 경로를 출력한다.

import heapq
INF = int(1e9)

N,M = map(int, input().rstrip().split(' '))
roads = {vertex: {} for vertex in range(0, M+1)}

for vertex in range(M):
    roads[vertex][vertex+1] = 1

for i in range(N):
    start, end, distance = map(int, input().rstrip().split(" "))
    if end > M: continue

    if end in roads[start]:
        roads[start][end] = min(roads[start][end], distance)
    else:
        roads[start][end] = distance

def dijkstra(start, roads, M):
    distances = [INF for _ in range(M+1)]
    heap = [(0, start)]
    distances[0] = 0

    while heap:
        cur_distance, cur = heapq.heappop(heap)

        if distances[cur] < cur_distance: continue

        for neighbor, weight in roads[cur].items():
            next_distance = cur_distance + weight

            if next_distance < distances[neighbor]:
                heapq.heappush(heap,(next_distance, neighbor))
                distances[neighbor] = next_distance

    return distances


def solution(N,M, roads):
    result = dijkstra(0,roads,M)
    print(result[M])
    return

solution(N,M,roads)