[ BOJ 1916 ] 최소 비용 구하기(Python)
문제
https://www.acmicpc.net/problem/1916
출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력하면 된다.
그나마 다행인(🤔) 점은 출발점에서 도착점을 갈 수 있는 경우만 주어진다는 것~
문제를 제대로 안읽어서 양방향으로 연결하고 한참 해맸다.
우어어 ༼;´༎ຶ ༎ຶ༽
특정한 최단 거리 를 풀고 이 문제를 풀었는데, 고려할 점이 적어서 쉽게 풀었다.
문제 풀이
- 출발 도시, 도착 도시를 단방향으로 이어주는 그래프 만들기
- 그래프 상에서 출발 도시와 연결된 도시들로 이동해준다.
2-1. 출발 도시에서 다른 도시까지 최단으로 이동할 때 드는 비용을dist
리스트에 저장한다.
2-2.dist[이동할 도시]
의 값이(현재 비용 + 이동 비용)
보다 크면, 값을(현재 비용 + 이동 비용)
로 할당해준다.
( = 더 작은 값을 최단 비용으로 처리해준다. ) dist[도착 도시]
의 값을 출력해준다.dist[도착 도시]
= 출발 도시에서 도착 도시까지 걸리는 최단 비용이 저장 되어있다.
코드
import sys
import heapq
INF = sys.maxsize
input = sys.stdin.readline
def dijkstra(start_cost,start_node):
dist = [ INF for _ in range(n+1)]
dist[start_node] = 0
q = [(start_cost,start_node)]
while q:
print(dist)
p = heapq.heappop(q)
cur_cost, cur_node = p[0], p[1]
for next_cost, next_node in graph[cur_node]:
if dist[next_node] > cur_cost + next_cost:
dist[next_node] = cur_cost + next_cost
heapq.heappush(q, (dist[next_node],next_node))
return dist
# 도시 개수 n, 버스 개수 m
n = int(input().rstrip())
m = int(input().rstrip())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
start,end,cost = map(int,input().rstrip().rsplit())
graph[start].append((cost,end))
want1, want2 = map(int,input().rstrip().rsplit())
answer = dijkstra(0,want1)
print(answer[want2])
Author And Source
이 문제에 관하여([ BOJ 1916 ] 최소 비용 구하기(Python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@uoayop/BOJ-1916-최소-비용-구하기Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)