1005 ACM Craft

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

위상 정렬으로 해결할 수 있다. 한 정점에 연결되어 있는 이전의 모든 정점들 중 건설 시간이 가장 긴 정점이 최종적으로 현재 정점의 건설 시간에 영향을 준다. 따라서 이를 메모이제이션(Memoization) 하면서 갱신해간다. 최종적으로 indegree가 0인 시점에서 해당 정점이 건설해야 할 건물이면 그 정점의 d 배열값이 정답이다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
int t,n,k,x,y,w,ind[1001],time[1001],d[1001];
vector<int> a[1001];
 
int ts()
{
    queue<int> q;
    for(int i=1;i<=n;i++) if(!ind[i])
        d[i]=time[i],q.push(i);
    while(!q.empty())
    {
        int now=q.front(); q.pop();
        for(int next : a[now])
        {
            if(d[next]<d[now]+time[next])
                d[next]=d[now]+time[next];
            if(--ind[next]==0)
            {
                if(next==w) return d[next];
                q.push(next);
            }
        }
    }
}
 
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;i++) scanf("%d",&time[i]);
        while(k--)
        {
            scanf("%d %d",&x,&y);
            a[x].push_back(y);
            ind[y]++;
        }
        scanf("%d",&w);
        if(!ind[w]) printf("%d\n",time[w]);
        else printf("%d\n",ts());
        for(int i=0;i<1001;i++)
            ind[i]=time[i]=d[i]=0,a[i].clear();
        a->clear();
    }
    return 0;
}