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

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

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

그래프에서 최소 비용을 구하는 문제로 다익스트라 알고리즘이 사용되는 대표 문제입니다.

* 다익스트라 알고리즘: 한 노드에서 다른 모든 노드로의 최소 비용(=최단 거리)을 계산할 때 사용되는 방법

접근 방식

1. 입력된 모든 노드와 간선 정보를 저장

2. 다익스트라 알고리즘을 이용해서 출발 도시에서 모든 도시로의 최소 비용을 계산

3. 2단계에서 계산된 출발 도시에서 도착 도시로의 비용을 출력

전체 코드

제출 언어: Python3

시간: 424ms

''' 제출 언어: Python3 시간: 424ms ''' import sys import heapq def solution(c1): global graph, distance distance[c1] = 0 q = [ (0, c1) ] while q: cd, cc = heapq.heappop(q) if distance[cc] < cd: continue for nc, w in graph[cc]: nd = cd + w if distance[nc] > nd: distance[nc] = nd heapq.heappush(q, (nd, nc)) if __name__ == "__main__": N = int(sys.stdin.readline().strip()) M = int(sys.stdin.readline().strip()) graph = [ [] for _ in range(N+1) ] distance = [ float('inf') ] * (N+1) for _ in range(M): s, e, w = map(int, sys.stdin.readline().strip().split()) graph[s].append((e, w)) c1, c2 = map(int, sys.stdin.readline().strip().split()) solution(c1) answer = distance[c2] print(answer)

from http://coding-w00se.tistory.com/73 by ccl(A) rewrite - 2021-09-28 01:00:28