/****************************************************************************** Welcome to GDB Online. GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl, C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog. Code, Compile, Run and Debug online from anywhere in world. *******************************************************************************/ #include #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int t, n, k, w; std::cin >> t; for (int testcase = 0; testcase < t; testcase++) { std::cin >> n >> k; std::vector> adj; std::vector delay; std::vector indgree; std::vector ans; std::vector visited; adj.resize(n+1, std::vector()); delay.resize(n+1, 0); indgree.resize(n+1, 0); ans.resize(n+1); visited.resize(n+1, false); std::queue q; std::queue TS; for (int i = 1; i < n+1; i++) { std::cin >> delay[i]; ans[i] = delay[i]; } for (int i = 0; i < k; i++) { int x, y; std::cin >> x >> y; adj[x].push_back(y); indgree[y] += 1; } std::cin >> w; for (int i = 1; i < n+1; i++) { if (indgree[i] == 0) { q.push(i); } } while(!q.empty()) { int curr = q.front(); if (!visited[curr]) { visited[curr] = true; TS.push(curr); } q.pop(); for (int i = 0; i < adj[curr].size(); i++) { int next = adj[curr][i]; indgree[next] -= 1; } for (int i = 1; i < n+1; i++) { if (indgree[i] == 0 && !visited[i]) { q.push(i); } } } // 답 int a = TS.size(); for (int i = 0; i < a; i++) { int curr = TS.front(); TS.pop(); for (int j = 0; j < adj[curr].size(); j++) { int next = adj[curr][j]; ans[next] = std::max(ans[next], ans[curr] + delay[next]); } } std::cout << ans[w] << "\n"; } return 0; }

제출 #72050

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: