BAEKJOON 1005번: ACM Craft

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

1005번: ACM Craft

풀이

D[i]={i번째 건물을 짓는데 걸리는 총 시간}

D를 위와 같이 정의 하면, 마지막으로 짓고 싶은 건물 W에서 시작하여 각 건물에 대해 건물을 짓기 위해 필요한 건물들을 짓는데에 필요한 총 시간 중 최댓값만 가져오면 됩니다. 

 

코드

#include <bits/stdc++.h>
using namespace std;
vector<int>vi[1003];
int D[1003],dp[1003];
int f(int i){
    int &ret=dp[i];
    if(ret!=-1)return ret;
    dp[i]=0;
    for(int j=0;j<(int)vi[i].size();j++){
        ret=max(ret,f(vi[i][j]));
    }
    ret+=D[i];
    return ret;
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        memset(dp,-1,sizeof(dp));
        int N,K,X,Y,W;
        scanf("%d%d",&N,&K);
        for(int i=1;i<=N;i++)vi[i].clear();
        for(int i=1;i<=N;i++)scanf("%d",&D[i]);
        for(int i=1;i<=K;i++){
            scanf("%d%d",&X,&Y);
            vi[Y].push_back(X);
        }
        scanf("%d",&W);
        printf("%d\n",f(W));
    }
    return 0;
}