[BOJ-2056]작업

1005 문제와 비슷한데 이건 전체 건물 다 지었을 때! 최소시간을 구하는 것이다. 각 건물은 테크트리(선행조건이 있음!)가 정해진 입력값이 들어온다. 

이때 입력값에 대한 모든 건물을 짓는데 걸리는 최소시간을 출력하라 <= 이게 문제요약이다.

위상정렬만 해주고 그때 마다 값을 업데이트만 해주면 된다. 

그런데 100% 까지 가다가 Wrong Ans(틀렸습니다!) 를 받았다. 왜이지 하며 생각을 해봤는데....

다행히도 바로 코너 케이스가 생각이 났다.

3

100 0

2 0

3 0

이런 식의 입력이 들어왔을 때! 나는 0을 출력하고 있었다...... 정확한 답은 100이고 당연히 저기선 100이 나와야하는데... 생각해보니 degree.... 가 0 인 것은 업데이트 할 것이 없으면 업데이트를 안하고 있었다. 

그래서 코드에는 추가했고 주석을 달았다...

#include<cstdio>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
 
const int INF = 0x7FFFFFFF;
 
int main(){
    int n;
    int ans = 0;
    scanf("%d", &n);
    VVI adj = VVI(n+1, VI(0,0));
    VI cost = VI(n+1, 0);
    VI result = VI(n+1, 0);
    VI deg = VI(n+1, 0);
 
    queue<int> Q;
    for(int v = 1 ; v <= n ; v++){
        scanf("%d %d",&cost[v] ,&deg[v]);
        if(deg[v] == 0){
            Q.push(v);
            result[v] = cost[v];
        }
        for(int j = 0 ; j < deg[v] ; j++){
            int u;
            scanf("%d", &u);
            adj[u].push_back(v);
        }
    }
    
    while(!Q.empty()){
        int here = Q.front(); Q.pop();
        ans = (cost[here] > ans)? cost[here] : ans; // add code
 
        for(auto iter = adj[here].begin() ; iter != adj[here].end() ; iter++){
            int there = *iter;
            if(result[there] < cost[there] + result[here]){
                result[there] = cost[there] + result[here];
                ans = (result[there] > ans)? result[there] : ans;
            }
            deg[there]--;
            if(deg[there]==0){
                Q.push(there);
            }
        }
    }
    printf("%d",ans);
    return 0;
}
 
// 100% WA