(Python) - BOJ(1753번) : 최단경로

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

1753번: 최단경로

---

• 해설 : 

그래프에서 V와 E의 정보가 주어지고 시작점의 정보가 주어질 때, 시작점에서부터 다른 모든 V까지의 최단거리(가중치 합의 최솟값)을 구하는 문제이다. 쉽게 말하면 다익스트라 기본형 문제이다. 

 

 

 

---

• 풀이 :

다익스트라 알고리즘을 구현할 수 있는지 없는지를 묻는 문제이다.

다익스트라는 알고리즘중 구현이 쉽지 않기 때문에 단순 구현이지만 골드5의 난이도를 부여받은 것 같다.

 

 

 

---

• 소스코드 : 

 

from heapq import heappop,heappush
import sys
def dijkstra(start):
    heap = []
    answer[start] = 0
    heappush(heap, [0, start])
    while heap:
        w, n = heappop(heap)
        for n_n, wei in weight[n]:
            n_w = wei + w
            if n_w < answer[n_n]:
                answer[n_n] = n_w
                heappush(heap, [n_w, n_n])
 
if __name__ == "__main__":
    V,E = map(int,sys.stdin.readline().split())
    start = int(sys.stdin.readline())
    weight = [[] for _ in range(V+1)]
    answer = [10000000]*(V+1)
    for _ in range(E):
        a,b,c = map(int,sys.stdin.readline().split())
        weight[a].append([b,c])
    dijkstra(start)
    for ans in answer[1:]:
        if ans == 10000000:
            print("INF")
        else:
            print(ans)