[Algorithm] 1005: ACM_Craft

📦1005: ACM_Craft

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-20
문제 확인하기

풀이

• 위상 정렬 문제이다.
• 건설 순서가 주어지기 때문에 Indegree를 통해서 순서를 뒤로 미뤄준다.
• Res[i][j] 은 i 번째 건물을 건설 완료하는데 발생하는 최소 시간을 말한다.
• Res에 업데이트 할 때는 문제에서 제시한 대로 늦는 건물에 시간을 맞춰야 하기 때문에 소요 시간이 더 큰 건물로 계산한다.

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#define endl '\n'
using namespace std;
 
int T, N, K, a, b, goal;
int Time[1001];
vector<int> Sequence[1001];
int Indegree[1001];
int Res[1001];
 
void Input(){
    cin >> N >> K;
    for(int i = 1; i <= N; i++){
        cin >> Time[i];
    }
    for(int i = 0; i < K; i++){
        cin >> a >> b;
        Sequence[a].push_back(b);
        Indegree[b]++;
    }
    cin >> goal;
}
 
void Initialize(){
    for (int i = 0; i < N; i++) Sequence[i].clear();
    memset(Time, 0, sizeof(Time));
    memset(Res, 0, sizeof(Res));
    memset(Indegree, 0, sizeof(Indegree));
}
 
void Solution(){
    queue<int> q;
    for(int i = 1; i <= N; i++){
        if(Indegree[i]==0){
            q.push(i);
            Res[i] = Time[i];
        }
    }
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(auto nxt : Sequence[cur]){
            Res[nxt] = (Res[nxt] < Res[cur]+Time[nxt]) ? Res[cur]+Time[nxt] : Res[nxt];
            Indegree[nxt]--;
            if(Indegree[nxt]==0){
                q.push(nxt);
            }
        }
    }
    cout << Res[goal] << endl;
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> T;
    while(T--){
        Input();
        Solution();
        Initialize();
    }
 
    return 0;
}