1005번: ACM Craft

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


$O(n)$

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N = 1e3;
int t, n, m, w, s[MAX_N + 1], ck[MAX_N + 1];
vector<int> adj[MAX_N + 1];
int dfs(int h) {
    if (ck[h]) return s[h];
    ck[h] = 1;
    int maxi = 0;
    for (auto it : adj[h]) maxi = max(maxi, dfs(it));
    return s[h] += maxi;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%d", s + i), adj[i].clear(), ck[i] = 0;
        for (int i = 0, x, y; i<m; i++) scanf("%d %d", &x, &y), adj[y].push_back(x);
        scanf("%d", &w);
        printf("%d\n", dfs(w));
    }
    return 0;
}