백준 1916 최소비용 구하기

https://www.acmicpc.net/problem/1916

 

 이 문제는 도시 간의 버스비용이 최소로 해서 출발지와 도착지로 가는 버스비용 중 가장 최소비용을 구하는 문제이다. 이 문제는 정확히 데이크스트라 알고리즘(다익스트라 알고리즘이라고도 불림)을 사용하는 문제이다. 데이크스트라 알고리즘은 거칠게 설명하자면 그래프를 탐색하면서 내가 지나온 비용을 들고 탐색하고, 도시에 도착할 때 마다 그 전의 최소비용과 비교하며 지금이 더 최소라면 새로 업데이트 하는 식으로 한 도시에서 다른 도시로 가는 최소비용을 구하는 알고리즘이다.

 

import sys
input = sys.stdin.readline
import heapq


            
cities = int(input().rstrip())
buses = int(input().rstrip())

graph = [[] for _ in range(cities+1)]

for i in range(buses):
    a,b,cost = map(int,input().rstrip().split())
    graph[a].append([cost,b])

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

heap=[]
costs = [1e9 for _ in range(cities+1)]
costs[start] = 0
heapq.heappush(heap,[0,start])

while heap:
    now_cost,now_node = heapq.heappop(heap)
    if costs[now_node] < now_cost:
        continue
    for next_cost,next_node in graph[now_node]:
        sum_cost = now_cost + next_cost
        if sum_cost >= costs[next_node]:
            continue
        costs[next_node] = sum_cost
        heapq.heappush(heap,[sum_cost,next_node])

print(costs[end])

https://velog.io/@ssh00n/%EB%B0%B1%EC%A4%80-1916-%EC%B5%9C%EC%86%8C%EB%B9%84%EC%9A%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘]백준 1916 : 최소비용 구하기 (파이썬)

 

필자는 위 블로그를 참고하여 코드를 짰다. 데이크스트라 알고리즘을 짜는 것은 처음인지라, 세세한 부분에 대한 정보가 필요하여 사실상 카피를 했다.