fork(1) download
copy 
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <deque>
  8. #include <functional>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14. #include <sstream>
  15. #include <stack>
  16. #include <string>
  17. #include <vector>
  18.  
  19. using namespace std;
  20.  
  21. int M, N;
  22. string s;
  23.  
  24. #define FOR(i, N) for(int i = 0; i < N; i++)
  25. #define FOR1e(i, N) for(int i = 1; i <= N; i++)
  26. #define REP(i, M, N) for(int i = M; i < N; i++)
  27. #define REPe(i, M, N) for(int i = M; i <= N; i++)
  28. #define sc(N) scanf("%d", &N)
  29. #define scsc(M, N) scanf("%d %d", &M, &N)
  30. #define gt(s) getline(cin, s)
  31. #define all(s) s.begin(), s.end()
  32. #define ll long long
  33. #define ull unsigned ll
  34. #define vi vector <int>
  35. #define pii pair <int, int>
  36. #define SS stringstream
  37. #define pq priority_queue
  38. #define mp make_pair
  39. #define pb push_back
  40. #define PI 3.14159265
  41. #define EPS 1e-7
  42.  
  43. const int MAX = 105;
  44. const int MOD = 1000000007;
  45.  
  46. struct edge{
  47. 	int from, to, w;
  48. 	bool station;
  49. 	edge(int from, int to, int w, bool station): from(from), to(to), w(w), station(station) {}
  50. 	edge() {}
  51. 	bool operator <(const edge &e) const{
  52. 		return w > e.w;
  53. 	}
  54. };
  55.  
  56. vector < vector <edge> > v;
  57. bool vis[510];
  58.  
  59. int dijkstra(int src){
  60. 	vi dist(505, 1e9); dist[src] = 0;
  61. 	pq <edge> q; q.push(edge(-1, src, 0, 0));
  62. 	while(q.size()){
  63. 		edge e = q.top(); q.pop();
  64. 		if(vis[e.to])
  65. 			return dist[e.to];
  66. 		if(e.w > dist[e.to])
  67. 			continue;
  68. 		FOR(i, v[e.to].size()){
  69. 			edge ne = v[e.to][i];
  70. 			if(dist[ne.to] > ne.w+dist[ne.from]){
  71. 				dist[ne.to] = ne.w+dist[ne.from];
  72. 				q.push(ne);
  73. 			}
  74. 		}
  75. 	}
  76. 	return -1;
  77. }
  78.  
  79. int main(){
  80. //	freopen("in.txt", "r", stdin);
  81. 	int t; sc(t);
  82. 	string line; cin.ignore(); gt(line);
  83. 	while(t--){
  84. 		int n, m; scsc(n, m);
  85. 		v = vector < vector <edge> >(510);
  86. 		memset(vis, 0, sizeof vis);
  87. 		FOR(i, n){
  88. 			int x; sc(x);
  89. 			vis[x] = 1;
  90. 		}
  91. 		cin.ignore();
  92. 		while(gt(line) && line.size()){
  93. 			SS ss(line);
  94. 			int a, b, w;
  95. 			bool f = 0;
  96. 			ss >> a >> b >> w;
  97. 			if(vis[a])
  98. 				f = 1;
  99. 			v[a].push_back(edge(a, b, w, f));
  100. 			if(!vis[b])
  101. 				v[b].push_back(edge(b, a, w, 0));
  102. 			else
  103. 				v[b].push_back(edge(b, a, w, 1));
  104. 		}
  105. 		int mn = 1e9, idx = 1;
  106. 		FOR1e(i, m)
  107. 			if(!vis[i]){
  108. 				vis[i] = 1;
  109. 				int mx = 0;
  110. 				FOR1e(j, m)
  111. 					if(j != i)
  112. 						mx = max(mx, dijkstra(j));
  113. 				if(mx < mn){
  114. 					mn = mx;
  115. 					idx = i;
  116. 				}
  117. 				vis[i] = 0;
  118. 			}
  119. 		printf("%d\n", idx);
  120. 		if(t)
  121. 			puts("");
  122. 	}
  123. 	return 0;
  124. }
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
1

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
stdout
copy 
5
https://ideone.com/CFplTS
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!