1. 문제 설명

아이템 제작

2. 문제 분석

다익스트라 알고리즘의 원리를 이용, 특정 노드로 갈 수 있는 비용이 업데이트되면 그 노드를 사용(경유)하는 다른 모든 노드에서도 업데이트되도록 한다. 이때 다익스트라 알고리즘 이전에서 거리 비용을 만들었는데, 여기에서는 문제 상황에서 곧바로 비용이 주어지므로 이를 사용하자. 거리 비용 역시 특정 노드 비용 두 개가 합쳐진 비용으로 계산되어야 한다.

3. 나의 풀이

import sys
import heapq

pq = []
n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
costs = [0] + list(map(int, sys.stdin.readline().rstrip().split()))
for i in range(1, n+1):
    heapq.heappush(pq, [costs[i], i])
for _ in range(m):
    made, used1, used2 = map(int, sys.stdin.readline().rstrip().split())
    nodes[used1].append([used2, made])
    nodes[used2].append([used1, made])

def Dijkstra():
    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        if costs[cur_node] < cur_cost: continue

        for next_used, next_made in nodes[cur_node]:
            if costs[next_made] > cur_cost + costs[next_used]:
                costs[next_made] = cur_cost + costs[next_used]
                heapq.heappush(pq, [cur_cost + costs[next_used], next_made])

Dijkstra()
print(costs[1])