[BOJ/백준] 1916. 최소비용 구하기 (Python)

🔎 문제

🔗 백준 1916번 최소비용 구하기

💡 풀이

음수 간선이 없고 최단거리 구하는 문제이므로 다익스트라로 풀이했다.

🔗 다익스트라 구현 (python) 에 다익스트라를 파이썬으로 구현 하는 방법을 정리해 놓으니 보면 되겠다.

📃 소스코드

import sys
import collections
import heapq
input = sys.stdin.readline

def dijkstra(start):
    # (소요시간, 정점)
    Q = [(0, start)]

    while Q:
        # 소요시간 가장 적은것 pop, Q최소힙
        time, node = heapq.heappop(Q)
        # 해당 노드에 처음 방문 할 때에만
        if node not in dist:
            dist[node] = time
            for v, w in graph[node]:
                alt = time + w
                heapq.heappush(Q, (alt, v))

# ------- 입력 받기 시작 ------
N = int(input())
M = int(input())

graph = collections.defaultdict(list)
for _ in range(M):
    # 출발, 도착, 버스비용
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

start, end = map(int, input().split())
# ------- 입력 받기 끝 ------

dist = collections.defaultdict(int) # 거리
dijkstra(start)

print(dist[end])

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️