[BOJ] 1753. 최단경로

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

1753번: 최단경로

 

 

1. 해결방법

"""
1. 아이디어
- 한 점 시작, 모든 거리 : 다익스트라
- 간선, 인접리스트 저장
- 거리 배열 무한대로 초기화
- 시작점 : 거리 배열 0, 힙에 넣어주기
- 힙이 빌떄까지 다음을 반복
    - 최신값인지 먼저 확인
    - 간선을 타고 간 비용이 더 작으면 갱신

2. 시간복잡도
- 다익스트라 : O(ElogV)

3. 자료구조
- heap : (비용, 노드번호)
- 거리 배열 : 비용 : int[]
- 인접리스트 : (비용, 노드번호)[]
"""

 

 

2. 정답코드

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

V, E = map(int, input().split())
K = int(input())

edge = [[] for _ in range(V + 1)]
dist = [INF] * (V + 1)

for i in range(E):
    u, v, w = map(int, input().split())
    edge[u].append([w, v])

heap = [[0, K]]
dist[K] = 0

while heap:
    ew, ev = heapq.heappop(heap)
    if dist[ev] != ew: continue
    for nw, nv in edge[ev]:
        if dist[nv] > ew + nw:
            dist[nv] = ew + nw
            heapq.heappush(heap, [dist[nv], nv])

for i in range(1, V + 1):
    if dist[i] == INF: print('INF')
    else:
        print(dist[i])

다익스트라의 기본문제이며 이 유형의 코드는 외워두는 것이 응용문제를 풀 때 수월하게 풀 수 가 있다. 
근데 이해가 어려워서,,