Gidhub BE Developer

BOJ - ACM Craft

2018-01-29
goodGid

Problem

Problem URL : ACM Craft

Screenshots of Problem Explain

Code



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

int main(){
    int tc;
    cin >> tc;
    
    while (tc--) {
        int arr_value[1001] ={0};
        int arr_cnt[1001] = {0};
        int dp_value[1001] = {0};
        
        int n,m;
        cin >> n >> m;
        
        vector<vector<int>> v;
        v.resize(n+1);
        
        for(int i=1; i<=n; i++)
            scanf("%d",&arr_value[i]);
        
        for(int i=1; i<=m; i++){
            int a,b;
            scanf("%d%d",&a,&b);
            v[a].push_back(b);
            arr_cnt[b] ++ ;
        }
        
        int goal;
        cin >> goal;
        
        queue<int> q;
        for(int i=1; i<=n; i++){
            if(arr_cnt[i] == 0){
                q.push(i);
                dp_value[i] = arr_value[i];
            }
        }

        
        while (! q.empty()) {
            int a;
            a = q.front();
            q.pop();
            
            for(int i=0; i<v[a].size(); i++){
                dp_value[ v[a][i] ] = max(dp_value[ v[a][i] ], dp_value[a] + arr_value[v[a][i]]);
                
                if( -- arr_cnt[ v[a][i] ] == 0)
                    q.push(v[a][i]);
            }
        }
        cout << dp_value[goal] << endl;
    }
    
    return 0;
}


Feed Back

  • 위상 정렬 문제는 Code가 대체로 길다.

  • 전형적인 코드 틀이 있는 듯하다.

  • 위상 정렬 알고리즘 문제를 처음 풀어봐서 좀 어색했는데 몇개더 풀어보니 익숙해짐 !


Back : Docker

Comments

Content