[BOJ] 1916. 최소비용 구하기 성공

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

1916번: 최소비용 구하기

 

 

1. 해결방법

"""
1. 아이디어
- 한 점에서 다른 점 까지의 최소 비용 : 다익스트라
- 간선, 인접리스트 저장
- 거리 배열을 무한대로 저장
- heap이 빌때까지 다음을 반복
    - 힙의 최솟값을 꺼내고 최신값인지 확인
    - 간선을 타고 간 비용이 dist[]보다 작으면 갱신
    - 해당 노드를 다시 heap에 push

2. 시간복잡도
- O(ElogV)

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

 

 

2. 정답코드

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

N = int(input())
M = int(input())

edge = [[] for _ in range(N + 1)]
for i in range(M):
    a, b, c = map(int, input().split())
    edge[a].append([c, b])

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

heap = [[0, start]]
dist = [INF] * (N + 1)
dist[start] = 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])

print(dist[end])

다익스트라 기본 알고리즘을 이용하면 문제 없이 풀 수 있다.
어찌됐든 다익스트라가 어떤 로직인지 그 로직을 코드로 어떻게 풀었는지는 무조건 알아야한다.