BOJ 5972 - 택배 배송

문제

백준 온라인 저지 - 5972번

풀이 과정

특정 시작 지점에서 목표 지점에 도달하기 위한 최소 비용을 찾는 문제입니다.
다익스트라 알고리즘 을 이용해서 한 정점에서 모든 정점까지의 최단 비용을 구하면 ElogV 의 시간 복잡도로 구할 수 있습니다.

코드

import sys
import heapq


INF = 2e9


def dijkstra(frm, to):
    dist = [INF] * (N + 1)
    pq = []

    dist[frm] = 0
    heapq.heappush(pq, [0, frm])

    while pq:
        cost, here = heapq.heappop(pq)

        if dist[here] < cost:
            continue

        for there, there_cost in graph[here]:
            next_cost = cost + there_cost
            if dist[there] > next_cost:
                dist[there] = next_cost
                heapq.heappush(pq, [next_cost, there])

    return dist[to]


def make_graph():
    graph = [[] for _ in range(N + 1)]

    for frm, to, cost in edges:
        graph[frm].append([to, cost])
        graph[to].append([frm, cost])

    return graph


def solution():
    answer = dijkstra(1, N)

    return answer


if __name__ == '__main__':
    N, M = list(map(int, sys.stdin.readline().split()))
    edges = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

    graph = make_graph()
    answer = solution()

    print(answer)