baekjun 1005. ACM Craft

 최솟값을 찾아라면서 최대값을 찾는 문제.  문제를 풀면서 자료구조의 범위 지정에 신경쓰는 연습을 해야할듯

#include <iostream>
#include <cstring>
#include <algorithm>
 
int N, K;
int minTimes[1001];
int cache[1002];
int connect[1001][1001];
int target;
 
using namespace std;
 
int getMinCraft(int target) {
    int &ret = cache[target];
    if (ret != -1)
        return ret;
    ret = minTimes[target];
    for (int i = 1; i <= N; i++)
        if (connect[target][i] == 1)
            ret = max(ret, getMinCraft(i) + minTimes[target]);
    return ret;
}
 
int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        cin >> N >> K;
        for (int i = 1; i <= N; i++)
            cin >> minTimes[i];
        memset(cache, -1, sizeof(cache));
        memset(connect, 0, sizeof(connect));
        
        for (int i = 1; i <= K; i++) {
            int y,x;
            cin >> y;
            cin >> x;
            connect[x][y] = 1;
        }
        cin >> target;
        cout << getMinCraft(target) << endl;
    }
    //system("pause");
    return 0;
}