백준 1005 ACM Craft 혼내주기

 

위상정렬 문제. 종만북에서 위상정렬을 dfs를 돌린다음 방문 순서의 역순을 출력함으로 해결했던 기억이 있었는데, 이번에는 모든 정점에서 자신에게 들어오는 정점들을 따로 벡터에 저장해서 해결했다.

 

target 정점을 시작으로, 자신에게 들어오는 정점 중 가장 시간이 오래 걸리는 정점을 재귀적으로 선택해서 건설 시간을 다 더하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int buildTime[1000], cache[1000];
vector<int> adj[1000];
vector<int> innode[1000];

int build(int target){
    
    int& ret = cache[target];
    if(ret != -1) return ret;

    if(innode[target].empty()) return ret = buildTime[target];
    
    ret = 0;
    for(int n : innode[target])
        ret = max(ret, build(n));
    
    return ret = ret + buildTime[target];
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, k, u, v, w;
        cin >> n >> k;
        memset(cache, -1, sizeof(cache));
        for(int i = 0; i < n; ++i){
            adj[i].clear();
            innode[i].clear();
        }

        for(int i = 0; i < n; ++i)
            cin >> buildTime[i];
        for(int i = 0; i < k; ++i){
            cin >> u >> v; --u; --v;
            adj[u].push_back(v);
            innode[v].push_back(u);
        }
        cin >> w; --w;
        cout << build(w) << "\n";
    }
}