코딩테스트 대비/단계별 코딩 테스트 준비(27일 과정)
[다익스트라/Python] 1916번: 최소비용 구하기 - 효과는 굉장했다!
bluetag_boy
2022. 2. 19. 17:01
반응형
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
알고리즘 분류
- 그래프 이론
- 다익스트라
SOLUTION
import sys
import heapq
INF = sys.maxsize
# 다익스트라 알고리즘
def dijkstar(start):
heap = []
distance[start] = 0 # 시작점의 가중치는 0
heapq.heappush(heap, (0, start))
while heap:
cost, now = heapq.heappop(heap)
# 최소비용으로 가는 것이 아니면 패스
if distance[now] < cost:
continue
for next_node, weight in graph[now]:
next_cost = cost + weight
# 최소 비용으로 가는 것이면 갱신 해줌
if next_cost < distance[next_node]:
distance[next_node] = next_cost
heapq.heappush(heap, (next_cost, next_node))
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)
# 그래프 생성
for _ in range(M):
c1, c2, cost = map(int, sys.stdin.readline().split())
graph[c1].append((c2, cost))
start, end = map(int, sys.stdin.readline().split())
dijkstar(start)
print(distance[end])