ACM Craft - 1005

//1005 - ACM Craft
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, K;
vector<vector<int>> adj;
int cost[1001];
int S;
int cache[1001];
 
void init()
{
    cin >> N >> K;
    for(int i = 1; i<=N; ++i)
        cache[i] = -1;
    adj = vector<vector<int>>(N+1);
    for(int i = 1; i<=N; ++i)
        cin >> cost[i];
    int x, y;
    for(int i = 0; i<K; ++i)
    {
        cin >> x >> y;
        adj[y].push_back(x);
    }
    cin >> S;
}
 
int dp(int idx)
{
    int& ret = cache[idx];
    if(ret != -1) return ret;
    ret = 0;
    for(int i = 0; i<adj[idx].size(); ++i)
    {
        int there = adj[idx][i];
        ret = max(ret, dp(there));
    }
    ret += cost[idx];
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        cout << dp(S) << "\n";
    }
}

 

 

 

 

 

 

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

1005번: ACM Craft

 

 

 

 

 

 

ACM Craft

간선의 방향을 역으로 연결하고 dp를 이용해 해결했습니다

C[idx] : idx건물을 완성하는데 걸리는 최소시간

C[idx]는 연결되어있는 다른건물들의 완성시간중 가장 오래걸리는 시간에 idx건물을 짓는 시간을 더해주면 됩니다!