위상 정렬을 할 줄 안다면 어렵지 않게 풀 수 있는 문제이다. 나는 BFS를 통한 위상 정렬을 이용했다. 위상 정렬을 통해 처음부터 W
까지 순차적으로 방문하면서 방문한 정점의 가중치, 즉 건설 시간을 누적으로 합하여 int dp[1001]
에 저장하였다. 최종 건설 시간은 결국 간선이 연결된 정점들의 최대 가중치의 합이므로 최댓값을 찾아 저장해주고 dp[W]
에 최종 시간이 남게 된다.
위상 정렬 문제는 전에 한번 풀어봤기에 알고리즘을 생각하는데는 어려움이 없었지만 가중치 합을 구하는 과정에서 시간이 좀 오래 걸렸다. dp
문제를 좀 더 풀어봐야겠다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int T, N, K, W;
int D[1001];
vector<int> v[1001];
int inDegree[1001];
int dp[1001];
void solution() {
queue<int> q;
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) {
q.push(i);
dp[i] = D[i];
}
}
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == W) break;
for (int i = 0; i < v[cur].size(); i++) {
int next = v[cur][i];
inDegree[next]--;
dp[next] = max(dp[next], dp[cur] + D[next]);
if (inDegree[next] == 0) {
q.push(next);
}
}
}
cout << dp[W] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> T;
while (T--) {
memset(D, 0, sizeof(D));
memset(v, 0, sizeof(v));
memset(inDegree, 0, sizeof(inDegree));
memset(res, 0, sizeof(res));
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> D[i];
}
for (int i = 0; i < K; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
inDegree[b]++;
}
cin >> W;
solution();
}
return 0;
}