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

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

1916번: 최소비용 구하기

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 그래프 이론
• 다익스트라

 

---

 

⊙ 문제 접근 과정

 

가장 짧은 경로를 구하는 문제다.

다익스트라 알고리즘으로 풀면 된다.

 

heapq 라이브러리를 사용해 우선순위 큐를 구현하자!

 

입력받은 출발점을 기준으로 각 정점간의 최소비용을 구해준 후, 도착지점의 최소 비용을 출력해주면 된다.

 

---

 

⊙ 문제 풀이

 

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
INF = 1e9

N = int(input())
M = int(input())
graph = [[] for _ in range(N)]
dp = [INF]*N
heap = []

for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u-1].append([v-1, w])

start, end = map(int, input().split())


def dijkstra(K):
    dp[K-1] = 0
    heappush(heap, [0, K-1])
    while heap:
        cost, pos = heappop(heap)
        if dp[pos] < cost:
            continue
        for p, c in graph[pos]:
            c += cost
            if c < dp[p]:
                dp[p] = c
                heappush(heap, [c, p])


dijkstra(start)

print(dp[end-1])

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!