백준/문제풀이_python
1916 최소비용 구하기
휴대용치즈
2023. 1. 7. 17:26
https://www.acmicpc.net/problem/1916
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
문제 접근
다익스트라 알고리즘 문제.
dfs로 풀릴것 같지만 시간초과로 틀릴것 같다. 시도해보진 않았다.
"""
다익스트라 알고리즘
-변수-
ans: 최종 비용을 저장해둠
heap: 가중치를 계산하기위해 사용하는 힙
graph: 입력으로 주어지는 그래프를 저장 [다음 노드, 다음 가중치]
-dfs대신 heap을 사용한 다익스트라를 사용하는 이유-
dfs를 사용하면 모든 경우를 선형탐색하지만,
다익스트라를 사용하면 최단거리를 먼저 검색하기 때문에 더 빨리 찾을수 있음
"""
코드
import heapq
import sys
input = sys.stdin.readline
"""
다익스트라 알고리즘
-변수-
ans: 최종 비용을 저장해둠
heap: 가중치를 계산하기위해 사용하는 힙
graph: 입력으로 주어지는 그래프를 저장 [다음 노드, 다음 가중치]
-dfs대신 heap을 사용한 다익스트라를 사용하는 이유-
dfs를 사용하면 모든 경우를 선형탐색하지만,
다익스트라를 사용하면 최단거리를 먼저 검색하기 때문에 더 빨리 찾을수 있음
"""
N = int(input())
M = int(input())
ans = [float('inf')] * (N+1)
graph = [[] for i in range(N+1)]
for i in range(M):
start, end, weight = map(int,input().split())
graph[start].append((weight, end))
def dijkstra(start):
heap = [(0, start)]
while heap:
w1, node = heapq.heappop(heap)
if ans[node] < w1:
continue
for w2, end in graph[node]:
if w1 + w2 < ans[end]:
ans[end] = w1 + w2
heapq.heappush(heap, (w1 + w2, end))
s, e = map(int,input().split())
dijkstra(s)
print(ans[e])| 57252 | 284 |