1005 c++ - ACM Craft

위상정렬을 사용하면 쉽게 풀 수 있습니다.

[그래프/정렬/유향] 위상정렬 / Topological Sorting

1516번 문제와 거의 동일한 문제. 단 w의 값을 출력해주면 됩니다.

#include <iostream>
#include <queue>
#include <vector>

#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int main() {
  fastio;
  int t;
  cin >> t;
  for (int i = 0; i < t; ++i) {
    int n, k;
    cin >> n >> k;

    vector<vector<int>> priorityBuild(n + 1);
    vector<int> buildTime(n + 1, 0);
    vector<int> totalTime(n + 1, 0);
    vector<int> inDegree(n + 1, 0);

    for (int j = 1; j <= n; j++) {
      cin >> buildTime[j];
      totalTime[j] = buildTime[j];
    }

    for (int j = 1; j <= k; j++) {
      int a, b;
      cin >> a >> b;
      priorityBuild[a].push_back(b);
      inDegree[b]++;
    }

    int w;
    cin >> w;

    queue<int> q;

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

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

      for (int next : priorityBuild[current]) {
        inDegree[next]--;

        totalTime[next] =
            max(totalTime[next], totalTime[current] + buildTime[next]);

        if (inDegree[next] == 0) {
          q.push(next);
        }
      }
    }

    cout << totalTime[w] << "\n";
  }

  return 0;
}