BOJ 1916번: 최소비용 구하기

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

아이디어:

앞선 다익스트라 구현 문제와 똑같은 문제이다.

이것도 기본문제니까 다시 풀어보자.

 

import sys, heapq

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    s, e, w = map(int, sys.stdin.readline().split())
    graph[s].append([e,w])
start, end = map(int, sys.stdin.readline().split())
INF = 999999999
cost = [INF]*(N+1) #비용 저장 배열

def solve(start, end):
    h = []
    cost[start] = 0
    heapq.heappush(h, [cost[start], start])

    while (h):
        now_cost, now_start = heapq.heappop(h)

        if (now_cost<cost[now_start]):
            continue

        for e, w in graph[now_start]:
            temp = now_cost + w
            if (temp<cost[e]):
                cost[e] = temp
                heapq.heappush(h, [cost[e], e])
    print(cost[end])
solve(start, end)