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

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

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

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)