[BOJ] 1005 ACM Craft

1. 문제링크

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

2. 문제해설

이 문제는 간단한 위상정렬 문제이다.

1. 각 노드까지 오는데 걸리는 시간을 저장하는 배열을 만든다.

2. 위상정렬을 하면서 축적하며 가장 큰 값들을 들고 온다.

3. 원하는 노드에 왔을 때 그 노드를 만드는데 걸리는 시간을 더한 후 출력한다.

3. 소스코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0);
#define NODE 1000

void testcase();

struct node{
    int e, w;
};

int main(){
    fio
    int t;
    cin >> t;
    while (t--) {
        testcase();
    }
    
    return 0;
}

void testcase(){
    int n, m, goal;
    int idegree[NODE+1] = {0};
    int delay[NODE+1] = {0};
    int ans[NODE+1] = {0};
    vector<int> edge[NODE+1];
    queue<int> q;
    
    cin >> n >> m;
    for (int i=1; i<=n; i++) {
        cin >> delay[i];
    }
    for (int i=0; i<m; i++) {
        int s, e;
        cin >> s >> e;
        edge[s].push_back(e);
        idegree[e]++;
    }
    cin >> goal;
    
    for (int i=1; i<=n; i++) {
        if (!idegree[i]) {
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for(int next : edge[cur]){
            ans[next] = max(delay[cur] + ans[cur], ans[next]);
            if(--idegree[next] == 0){
                if(next == goal){
                    ans[next] += delay[next];
                    cout << ans[goal] << '\n';
                    return;
                }
                q.push(next);
            }
        }
    }
}

4. 추가언급

마지막에 더하는 것을 까먹으면 틀린 답이 나올 수도 있다.