BOJ 1916번: 최소비용 구하기

호프 2021. 2. 13. 02:31

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

아이디어:

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

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

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)