백준 - 1005 ACM Craft

 

해결과정 - 위상정렬 , dp

처음에는 진입로가 없는 노드를 찾은뒤 그 노드부터 탐색해 나가면 된다고 생각하였다 그리고 중복을 방지하기위해 진입로의 개수를 저장해 둔뒤 진입로가 다 들어오면 그 노드에 진입할수 있도록 만들었는데 한가지 고려하지 않았던 점은 초기 집입로가 여러개 일 수도 있다는 것이였다. 이 사실만 고려하여 초기 진입로마다 탐색하게 만들어 준뒤 문제를 해결할수 있게 되었다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;


int main() {
    FAST;

    int T;
    cin >> T;

    while (T--) {
        int N, K;
        cin >> N >> K;

        vector<int> delay(N + 1);

        for (int i = 1; i <= N; i++) {
            cin >> delay[i];
        }

        vector <vector<int>> graph(N + 1);
        vector<int> indegree(N + 1, 0);

        for (int i = 0; i < K; i++) {
            int a, b;
            cin >> a >> b;
            graph[a].push_back(b);
            indegree[b]++;
        }

        int End;
        cin >> End;

        int Start;
        vector<int> dp(N + 1, 0);

        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                Start = i;
                queue<int> q;
                q.push(Start);
                dp[Start] = delay[Start];

                while (!q.empty()) {
                    int cur = q.front();
                    q.pop();

                    for (int i = 0; i < graph[cur].size(); i++) {
                        int next = graph[cur][i];
                        dp[next] = max(dp[next], dp[cur] + delay[next]);
                        indegree[next]--;
                        if (indegree[next] == 0) {
                            indegree[next] = -1;
                            q.push(next);
                        }
                    }
                }
            }
        }

        cout << dp[End] << '\n';
    }
    return 0;
}

 

후기

그래프 문제는 좀 익숙해진것 같은데 음 이건 골드 3수준은 아닌거 같다