[2637] 장난감 조립

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

2637번: 장난감 조립

"[1516] 게임 개발"과 비슷하게, 위상정렬 하면서 방문하게 되는 노드에 dp를 적용한다.

간선의 방향을 뒤집고, 항상 n부터 출발하도록 구현할 수 있다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, m, d[105], cost[105];

typedef struct {

    int idx, cost;

} state;

vector<state> adj[105];

queue<int> q;

bool chk[105];

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    int i;

    memset(chk, true, sizeof(chk));

    for (i = 0; i < m; i++) {

        int A, B, C;

        cin >> A >> B >> C;

        adj[A].push_back({B, C});

        d[B]++;

        chk[A] = false;

    }

    q.push(n);

    cost[n] = 1;

    while (!q.empty()) {

        int cur = q.front();

        q.pop();

        for (auto& nxt : adj[cur]) {

            d[nxt.idx]--;

            cost[nxt.idx] = cost[nxt.idx] + (cost[cur] * nxt.cost);

            if (d[nxt.idx] == 0) q.push(nxt.idx);

        }

    }

    for (i = 1; i < n; i++)

        if (chk[i]) cout << i << ' ' << cost[i] << '\n';

    return 0;

}

---