[Baekjoon Online Judge] 백준 1916번 최소비용 구하기(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1916번 최소비용 구하기

(Python)

(글쓴날 : 2020.06.09)

 

---

* Baekjoon Online Judge, 백준 1916번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1916번 최소비용 구하기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

---

2) 풀이 과정

* 시간 복잡도 : O(E log V)

 

N개의 도시와 M개의 버스 그리고 각 버스의 도시 구간 별 비용이 주어질 때, A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 구하는 문제입니다.

 

저의 경우, 다익스트라를 적용했으며, Python을 사용했습니다.

문제에서 입력되는 정보들을 인접 리스트에 구현한 뒤, 출발점인 A도시에 다익스트라를 적용하여 문제를 해결했습니다. 

---

3) 코드

 

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
def BFS(hq):
    while(hq):
        wei, vec = heapq.heappop(hq)
 
        if distance[vec] > wei:
            distance[vec] = wei
 
            for v, w in adjList[vec]:
                heapq.heappush(hq,(w+wei, v))
 
N = int(input())
M = int(input())
 
INF = 2147483647
distance = [INF] * (N+1)
adjList = [[] for _ in range(N+1)]
 
for _ in range(M):
    a,b,w = map(int,input().split())
    adjList[a].append((b,w))
 
S, A = map(int,input().split())
 
hq = []
 
for v, w in adjList[S]:
    heapq.heappush(hq, (w,v))
 
BFS(hq)
 
print(distance[A])

---