fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> ii;
  5.  
  6. const int N = 111, INF = (int)1e9;
  7.  
  8. vector <ii> G[N], S;
  9.  
  10. int V, E, dist[N], used[N][N], vis[N], all, cnt;
  11. int lev[N];
  12. int p[N];
  13.  
  14. void clear(void) {
  15. 	for (int i = 0; i <= V; ++i) {
  16. 		dist[i] = 0, vis[i] = 0;
  17. 		p[i] = -1;
  18. 		lev[i] = 0;
  19. 	}
  20. }
  21.  
  22. int bfs(ii cur) {
  23. 	int sum = 0;
  24. 	int s = cur.first, t = cur.second;
  25. 	int level = 0x7FFFFFFF;
  26. 	queue <int> q; q.push(s);
  27. 	dist[s] = 0;
  28. 	p[s] = 0;
  29. 	vis[s] = 1;
  30. 	while (!q.empty()) {
  31. 		int u = q.front(); q.pop();
  32. 		for (int i = 0; i < (int)G[u].size(); ++i) {
  33. 			ii v = G[u][i];
  34. 			if (v.first == t) {
  35. 				if (sum < dist[u] + v.second) {
  36. 					sum = dist[u] + v.second;
  37. 					dist[t] = sum;
  38. 					p[v.first] = u;
  39. 					level = lev[v.first] + 1;
  40. 				}
  41. 			} else	if (!vis[v.first]) {
  42. 				dist[v.first] = dist[u] + v.second;
  43. 				p[v.first] = u;
  44. 				++lev[v.first];
  45. 				q.push(v.first);
  46. 			}
  47. 		}
  48. 	}
  49. 	for (int i = t; i > 0; i = p[i]) vis[i] = 1;
  50. 	return sum;
  51. }
  52.  
  53. int main(void) {
  54. 	int tc; scanf("%d", &tc);
  55. 	while (tc--) {
  56. 		scanf("%d %d", &V, &E);
  57. 		S.clear();
  58. 		int s[4], t[4];
  59. 		for (int i = 0; i <= V; ++i) G[i].clear();
  60. 		for (int i = 0; i < 3; ++i) scanf("%d", &s[i]);
  61. 		for (int i = 0; i < 3; ++i) scanf("%d", &t[i]);
  62. 		for (int i = 0; i < 3; ++i) S.push_back(ii(s[i], t[i]));
  63. 		for (int i = 0; i < E; ++i) {
  64. 			int u, v, w; scanf("%d %d %d", &u, &v, &w);
  65. 			G[u].push_back(ii(v, w));
  66. 		}
  67. 		sort(S.begin(), S.end());
  68. 		int res = 0;
  69. 		bool flag = false;
  70. 		int x = 0;
  71. 		do {
  72. 			bool f = false;
  73. 			all = cnt = 0;
  74. 			for (int i = 0; i < 3; ++i) {
  75. 				x = bfs(S[i]);
  76. 				if (!x) {
  77. 					f = true; break;
  78. 				}
  79. 				all += x;
  80. 			}
  81. 			clear();
  82. 			if (f) continue;
  83. 			res = max(all, res);
  84. 		} while (next_permutation(S.begin(), S.end()));
  85. 		printf("%d\n", res);
  86. 	}
  87. 	return 0;
  88. }
Runtime error #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iRCSO0
language:
C++ (gcc 8.3)
created:
9 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!