[BOJ] 9946번 : 아이템 제작

Vermeil의 추천 문제.. 감사요!
이런 발상 쓰는 문제 처음 만나봐서 신기해서 글로 써둘까 한다.

---

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

9446번: 아이템 제작

---

풀이

일단 이 문제의 핵심은

x + y → a 와 같이 제작할 수 있다면,
간선 x → a의 비용은 y까지의 최소 비용,
간선 y → a의 비용은 x까지의 최소 비용

이라는 점이다.
처음에는 0번 정점에서 시작해서 아이템을 구매하는 것을 의미하는 간선을 추가하려 했다.
하지만, 다익스트라 돌리는 과정에서 '구매'와 '제작'을 구분해서 구현해야 해서 위 방법은 불편하다는 것을 깨달았다.

따라서, 처음에 모든 '구매'를 미리 처리해주어 다익스트라 돌릴 때에는 '제작'만 처리하면 되도록 하여 구현했다.

원래 내가 풀었던 다익스트라 문제들는 이미 간선의 비용이 정해진 이후에 다익스트라를 돌렸었는데,
이 문제는 간선의 비용이 다익스트라를 돌리는 과정에서 정해지는 점이 신기했다..

---

코드

ll n, m;
vector<pll> g[10005];
ll c[10005];
priority_queue<pll> pq;

ll dijkstra()
{
    pq.push({ 0, 0 });
    c[0] = 0;
    while (!pq.empty())
    {
        ll cost = -pq.top().X;
        ll now = pq.top().Y;
        pq.pop();
        if (cost > c[now]) continue;
        for (auto x : g[now])
        {
            ll nxt = x.X;
            ll nxtCost = cost + c[x.Y];
            if (nxtCost < c[nxt])
            {
                pq.push({ -nxtCost, nxt });
                c[nxt] = nxtCost;
            }
        }
    }
    return c[1];
}

void solve()
{
    cin >> n >> m;
    fill(c, c + 10005, LLONG_MAX);
    for (int i = 1; i <= n; i++)
    {
        ll x; cin >> x;
        pq.push({ -x, i });
        c[i] = x;
    }
    for (int i = 0; i < m; i++)
    {
        ll a, x, y; cin >> a >> x >> y;
        g[x].push_back({ a, y });
        g[y].push_back({ a, x });
    }
    cout << dijkstra();
}