[백준] 1916(파이썬) - 최소비용구하기

[백준] 1916(파이썬) - 최소비용구하기

728x90

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

이 문제는 다익스트라의 기본 중 기본문제이다.

먼저 각 인덱스 노드와 연결되어 있는 노드와 경로 값을 노드 번호를 인덱스로 가지고 있는 data리스트에 넣어준다.

dijkstra 함수에서는 heap구조를 이용해서 start 노드를 시작으로 놓고 구현했다.

q라는 리스트가 빌 때까지 while문을 돌려주면서 현재 비교하려는 노드와 그 노드가 가진 경로 값을 꺼내서 최단거리를 비교해준다. 최단거리를 갱신한 노드는 다시 확인하지 않아야 하기 때문에 continue를 넣어준다.

다음으로는 현재 비교하려는 노드를 인덱스로 하는 data값을 꺼내서 최소경로값과 꺼낸 비교하려는 노드까지 가는 경로 값을 더해서 cost라는 변수로 두고, cost가 비교하려는 노드에 저장된 최소 경로 값 보다 작으면 갱신해준 뒤에 비교한 노드와 갱신된 최소 경로값을 heap에 넣어주면 된다.

import sys,heapq input = sys.stdin.readline INF = 987654321 n = int(input()) m = int(input()) data = [[] for _ in range(n+1)] distance = [INF] * (n+1) for _ in range(m): # b가 노드 c 가 경로 a,b,c = map(int,input().split()) data[a].append((b,c)) start,end = map(int,input().split()) def dijkstra(start): q = [] heapq.heappush(q,(start,0)) distance[start] = 0 while q: # print(q) # print(data) # print(distance) now_node, dist = heapq.heappop(q) if distance[now_node] < dist: continue for n_n, weight in data[now_node]: cost = dist + weight if cost < distance[n_n]: distance[n_n] = cost heapq.heappush(q,(n_n,cost)) dijkstra(start) print(distance[end])

from http://resilient-923.tistory.com/338 by ccl(A) rewrite - 2021-08-25 15:00:15