fork download
  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
stdin
1

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10
stdout
5