[뱍쥰 1005번] ACM Craft

문제 링크: https://www.acmicpc.net/problem/1005

1005번: ACM Craft

<문제 풀이> 위상 정렬

 

기본적인 위상 정렬 알고리즘으로 최단거리를 구하면 되는데 주의할 점은

정점 v의 최단거리를 갱신할 때 u -> v에서 u의 건설 시간이 최대가 되는 정점을 택해야 한다.

(u의 모든 정점이 건설이 완료되어야 v를 건설할 수 있으므로 가장 늦게 건설이 완료되는 u를 택함)

dist[v] = max(dist[v], dist[u] + d[v]);

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
int n, k;
int d[1001];
vector<int> adj[1001];
int indegree[1001];
int dist[1001];
 
void bfs() {
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            Q.push(i);
            dist[i] = d[i];
        }
    }
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for (auto& v : adj[u]) {
            dist[v] = max(dist[v], dist[u] + d[v]);
            indegree[v]--;
            if (indegree[v] == 0) {
                Q.push(v);
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int test_case; cin >> test_case;
    while (test_case--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> d[i];
        }
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            indegree[y]++;
        }
        int w; cin >> w;
        bfs();
        cout << dist[w] << '\n';
        fill(dist, dist + 1001, 0);
        fill(indegree, indegree + 1001, 0);
        fill(d, d + 1001, 0);
        for (int i = 0; i < 1001; i++) {
            adj[i].clear();
        }
 
 
    }
 
    return 0;
}