[BOJ] 2637 장난감 조립

문제

2637번: 장난감 조립

우리는 어떤 장난감을 여러 가지 부품으로 조립하여 만들려고 한다. 이 장난감을 만드는데는 기본 부품과 그 기본 부품으로 조립하여 만든 중간 부품이 사용된다. 기본 부품은 다른 부품을 사용하여 조립될 수 없는 부품이다. 중간 부품은 또 다른 중간 부품이나 기본 부품을 이용하여 만들어지는 부품이다.

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

풀이

코드

#include <cstdio>
#include <queue>
using namespace std;

struct info {
    int cost, e;
};

int n, m;
vector<info> v[100];
int inDegree[100];
int chk[100];
int ans[100];

void go() {
    queue<int> q;
    q.push(n-1);

    for(int i = 0; i < n; i++) {
        int t = q.front(); q.pop();
        for(auto j : v[t]) {
            if (ans[t] == 0) ans[j.e] = j.cost;
            else ans[j.e] += ans[t]*j.cost;
            if (--inDegree[j.e] == 0) q.push(j.e);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    int a, b, c;
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        a--; b--;
        v[a].push_back({c, b});
        inDegree[b]++;
        chk[a] = 1;
    }
    go();
    for(int i = 0; i < n; i++) {
        if (chk[i] == 0) printf("%d %d\n", i+1, ans[i]);
    }
}