BOJ 1916 - 최소비용 구하기

문제

백준 온라인 저지 - 1916번

풀이 과정

한 정점으로부터 다른 모든 정점까지의 경로 정보를 사용해 최단 거리를 구하는 문제입니다.

최악의 경우 V = 1000이고 E = 100,000 이므로 O(ElgV) 의 시간 복잡도를 가지는 다익스트라 알고리즘 을 사용해서 답을 구할 수 있습니다.

코드

import sys
import heapq


N = int(input())
M = int(input())

adj = [[] for _ in range(1001)]
for _ in range(M):
    frm, to, cost = list(map(int, sys.stdin.readline().split()))
    adj[frm].append([to, cost])
start, goal = list(map(int, sys.stdin.readline().split()))


def dijkstra():
    pq = []
    dist = [sys.maxsize] * (N+1)

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

    while pq:
        here = heapq.heappop(pq)

        if dist[here[1]] < here[0]:
            continue

        for near in adj[here[1]]:
            next_dist = near[1] + here[0]

            if next_dist < dist[near[0]]:
                dist[near[0]] = next_dist
                heapq.heappush(pq, (next_dist, near[0]))

    return dist[goal]


def solution():
    answer = dijkstra()
    return answer


print(solution())