[백준] 1916번: 최소비용 구하기 문제 풀이 파이썬
문제 링크
https://www.acmicpc.net/problem/1916
풀이 방식
기존에 사용해왔던 다익스트라 방식을 사용하면 된다.
지금껏 풀어왔던 다익스트라 문제들과 크게 다를것이 없는 문제이다.
전체 코드
from sys import stdin
import heapq
INF = int(1e9)
def dijkstra(i, destination):
queue = []
heapq.heappush(queue, (0, i))
costList = [INF] * (N+1)
costList[i] = 0
while queue:
cost, city = heapq.heappop(queue)
if costList[city] < cost:
continue
for node_city, node_cost in graph[city]:
new_cost = cost + node_cost
if costList[node_city] > new_cost:
costList[node_city] = new_cost
heapq.heappush(queue, (new_cost, node_city))
return costList[destination]
N = int(input())
M = int(input())
graph = {}
for i in range(1, N+1):
graph[i] = []
for _ in range(M):
start, end, cost = map(int, stdin.readline().split())
graph[start].append([end, cost])
start_city, destination = map(int, stdin.readline().split())
print(dijkstra(start_city, destination))
Author And Source
이 문제에 관하여([백준] 1916번: 최소비용 구하기 문제 풀이 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyuntall/백준-1916번-최소비용-구하기-문제-풀이-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)