January 20, 2023

1916번: 최소비용 구하기

문제 요약

• N개의 도시와 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 주어졌을 때, A번째 도시에서 B번째 도시까지 가는데 드는 최소비용 출력
• 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 0 ≤ 버스 비용 ≤ 100,000

문제 풀이

from sys import maxsize, stdin
import heapq

input = stdin.readline

N = int(input())
M = int(input())
dis_list = [maxsize] * (N + 1)
edge_list = [[] for _ in range(N + 1)]
heap = []

for _ in range(M):
    start, end, cost = map(int, input().split())
    edge_list[start].append((end, cost))

start, end = map(int, input().split())

def dijkstra():
    dis_list[start] = 0
    heapq.heappush(heap, (0, start))

    while (heap):
        cost, now = heapq.heappop(heap)

        if (dis_list[now] < cost):
            continue

        for edge in edge_list[now]:
            next_cost = cost + edge[1]
            if (dis_list[edge[0]] > next_cost):
                dis_list[edge[0]] = next_cost
                heapq.heappush(heap, (next_cost, edge[0]))

dijkstra()

print(dis_list[end])

• 다익스트라 이용
• input 을 sys.stdin.readline 으로 대체하지 않으면 Python3 기준 시간초과 발생