[C++] 백준(BAEKJOON) 1005

 
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
     
    int t;
    int n, k, endPoint;
    int delay[1001];
    int path[1001][1001];
    int cache[1001];
    
    int dp(int x) {
        if (cache[x] != 0) 
            return cache[x];
        
        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (path[x][i]) {
                result = max(result, dp(i));
            }
        }
        return cache[x] = result + delay[x];
    }
     
    int main() {
        cin >> t;
        while (t--) {
            cin >> n >> k;
            
            for (int i = 1; i <= n; i++) {
                cin >> delay[i];
            }
            
            for (int i = 0; i < k; i++) {
                int a, b;
                cin >> a >> b;
                path[b][a] = true;
            }
            
            cin >> endPoint;
            cout << dp(endPoint) << '\n';
            
            memset(delay, 0, sizeof(delay));
            memset(path, 0, sizeof(path));
            memset(cache, 0, sizeof(cache));
        }
        return 0;
    }