최소비용 구하기

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라 정말 기본적인 다익스트라 문제! 따로 키 리스트를 설정하지 않아도 쉽게 풀 수 있다. 💻소스 코드 import sys import heapq input = sys.stdin.readline def dijkstra(s, e): pq = [] heapq.heappush(pq, (0, s)) # 출발지로 가는데 0원의 비용 visited = [0] * (N + 1) while pq: cost, w = heapq.heappop(pq) if w == e: return cost if visited[w]: continue visited[w] = 1 for newt_w, next_cost in adj[w]: if not visited[newt_w]: heapq.heappush(pq, (..

[python] 백준 - 1916. 최소비용 구하기

🤔문제 해결 G5 | 다익스트라, 그래프 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 알고리즘 간선, 최소 등등 말이 나오면 다익스트라? 나의 경우 다익스트라를 풀 때 항상 우선순위 큐를 이용한다. (파이썬의 힙큐를 사용) A 에서 갈 수 있는 모든 정점들의 최소비용을 리스트에 담아두고 B 지점을 답으로 출력한다. 먼저 (가중치, 시작점)을 힙큐에 넣고 시작한다. 시작점에서 각 정점까지의 비용은 가장 큰 값(파이썬에서 float('inf')를 넣어두고 시작한다.) 힙큐에서 값을 하나씩 꺼낸다. 꺼낸 정점에서 이웃한 정점들 중에서 아직 방문하지 않았고, 이웃한 정점까지의 비용보다 현재비용 + 꺼낸 정점에서 이웃한 정점까지의 간선비용이 작으면 각 정점까지의 비용을 현재비용 + 꺼낸 정점에서 이웃한..