fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <stack>
  4. #include <vector>
  5. #include <queue>
  6. #include <cstring>
  7. using namespace std;
  8. int t, n, k, w;
  9. int idx = 10001;
  10. int make[1004];
  11. int indegree[1004];
  12. vector<vector<int>> a;
  13. queue <int> q;
  14. bool visited[1001];
  15. int dp[1004];
  16. void bfs(int x) {
  17. 	visited[x] = true;
  18. 	while (!q.empty()){
  19. 			int here = q.front();
  20. 			q.pop();
  21. 			for (int i = 0; i < a[here].size(); i++) {
  22. 				int nhere = a[here][i];
  23. 				dp[nhere] = max(dp[nhere], dp[here] + make[nhere]);
  24. 				indegree[nhere]--;
  25. 				if (indegree[nhere] == 0)
  26. 					q.push(nhere);
  27. 			}
  28. 	}
  29. }
  30. int main(){
  31. 	scanf("%d", &t);
  32. 	while (t--){
  33. 		scanf("%d%d", &n, &k);
  34. 		a.clear();
  35. 		a.resize(n+1);
  36. 		memset(make, 0, sizeof(make));
  37. 		memset(dp, 0, sizeof(dp));
  38. 		memset(visited, false, sizeof(visited));
  39. 		memset(indegree, 0, sizeof(indegree));
  40. 		for (int i = 1; i <= n; i++) {
  41. 			scanf("%d", &make[i]);
  42. 		}
  43. 		for (int i = 1; i <= k; i++) {
  44. 			int u, v;
  45. 			scanf("%d%d", &u, &v);
  46. 			a[u].push_back(v);
  47. 			indegree[v]++;
  48. 		}
  49. 		for (int i = 1; i <= n; i++){
  50. 			if (indegree[i] == 0){
  51. 				q.push(i);
  52. 				idx = min(i,idx);
  53. 				//dp[i] = make[i];
  54. 			}
  55. 		}
  56. 		scanf("%d", &w);
  57. 		bfs(idx);
  58. 		printf("%d\n",make[idx]+dp[w]);
  59. 	}
  60. 	return 0;
  61. }
Success #stdin #stdout 0s 15256KB
comments (?)
stdin
copy 
1
3 2
1 2 1
1 3
2 3
3
stdout
copy 
2
https://ideone.com/CQXECS
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!