9446번: Dwarf Tower

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

1. 다익스트라 알고리즘을 응용해서 풀 수 있다.
2. 현재까지 최소 비용을 구한 아이템 집합을 S라 하자.
3. 초기에는 제작 비용이 가장 싼 아이템이 S에 포함되어있다.
4. S이외의 아이템을 S로부터 제작 혹은 구매를 할 때 최소 비용과 해당 아이템을 각각 c, p라고 하자.
5. 앞으로 어떠한 방법을 사용해도 비용은 c보다 작을 수 없으므로 p를 만들기 위한 최소 비용은 c이다. 이 t를 S에 포함시킨다.
6. 이 그리디 알고리즘을 반복하면 각각의 아이템를 얻기위한 최소 비용을 모두 구할 수 있다.

시간복잡도는 $O((m+n)\lg(m+n))$

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, m, cost[10001];
priority_queue<pair<int, int> > pq;
vector<pair<int, int> > v[10001];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", cost + i), pq.push({ -cost[i],i });
    for (int i = 0, a, x, y; i < m; i++) {
        scanf("%d%d%d", &a, &x, &y);
        v[x].push_back({ y,a });
        v[y].push_back({ x,a });
    }
    while (!pq.empty()) {
        int c = -pq.top().first, p = pq.top().second;
        pq.pop();
        if (cost[p] ^ c) continue;
        cost[p] = c;
        for (auto it : v[p]) if (cost[it.second]>c + cost[it.first]) {
            cost[it.second] = c + cost[it.first];
            pq.push({ -cost[it.second],it.second });
        }
    }
    printf("%d", cost[1]);
    return 0;
}