백준 1005번 ACM Craft C++

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

1005번: ACM Craft

 

위상 정렬

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

vector<int> inDegree;
vector<int> cost;
vector<int> totalCost;
vector<vector<int>> graph;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        int n, k, w;
        cin >> n >> k;

        inDegree = vector<int>(n + 1, 0);
        cost = vector<int>(n + 1);
        totalCost = vector<int>(n + 1, 0);
        graph = vector<vector<int>>(n + 1, vector<int>());

        for (int i = 1; i <= n; i++) {
            int c;
            cin >> c;
            cost[i] = c;
        }

        for (int i = 0; i < k; i++) {
            int start, end;
            cin >> start >> end;
            graph[start].push_back(end);
            inDegree[end]++;
        }
        cin >> w;

        queue<int> q;
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) q.push(i);
        }

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            for (int next : graph[curr]) {
                totalCost[next] = max(totalCost[next], totalCost[curr] + cost[curr]);
                if (--inDegree[next] == 0) q.push(next);
            }
        }
        int ans = totalCost[w] + cost[w];
        cout << ans << "\n";
    }
}