fork(2) download
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <string.h>
  4. #include <iostream>
  5. #include <vector>
  6. #include <list>
  7. #include <string>
  8. #include <algorithm>
  9. #include <queue>
  10. #include <stack>
  11. #include <set>
  12. #include <map>
  13. #include <complex>
  14. #include <assert.h>
  15. #define MAX_N 200005
  16. #define INF 1000000000000000LL
  17. using namespace std;
  18. typedef long long ll;
  19.  
  20. int n;
  21. set<int> parent[MAX_N];
  22. int color[MAX_N];
  23. struct Node
  24. {
  25. ll dist;
  26. vector<int> adj;
  27. vector<ll> weight;
  28. };
  29. Node graf[MAX_N];
  30. bool mark[MAX_N];
  31. struct pq_entry
  32. {
  33. ll node, dist;
  34. bool operator <(const pq_entry &a) const
  35. {
  36. if (dist != a.dist) return (dist > a.dist);
  37. return (node > a.node);
  38. }
  39. };
  40. inline void Dijkstra(int source)
  41. {
  42. priority_queue<pq_entry> pq;
  43. pq_entry P;
  44. for (int i=0;i<n;i++) {
  45. mark[i] = 0; parent[i].clear();
  46. if (i == source)
  47. {
  48. graf[i].dist = 0;
  49. P.node = i;
  50. P.dist = 0;
  51. pq.push(P);
  52. }
  53. else graf[i].dist = INF;
  54. }
  55. while (!pq.empty())
  56. {
  57. pq_entry curr = pq.top();
  58. pq.pop();
  59. int nod = curr.node;
  60. ll dis = curr.dist;
  61. for (int i=0;i<graf[nod].adj.size();i++)
  62. {
  63. if (!mark[graf[nod].adj[i]])
  64. {
  65. int nextNode = graf[nod].adj[i];
  66. if(dis + graf[nod].weight[i] == graf[nextNode].dist){
  67. parent[nextNode].insert(nod);
  68. }
  69. else if ((dis + graf[nod].weight[i]) < graf[nextNode].dist) {
  70. parent[nextNode].clear(); parent[nextNode].insert(nod);
  71. graf[nextNode].dist = dis + graf[nod].weight[i];
  72. P.node = nextNode;
  73. P.dist = graf[nextNode].dist;
  74. pq.push(P);
  75. }
  76. }
  77. }
  78. mark[nod] = true;
  79. }
  80. }
  81. int S[MAX_N], mark_pa[MAX_N], m;
  82. set<int> ss;
  83. vector<int> ans_v;int cnt;
  84. int dfs(int u, int pa) {
  85. cnt++;
  86. //if(cnt >= m) assert(0);
  87. int ans = 0; if(ss.find(u) != ss.end()) ans++;
  88. int maxi = 0, x = u;
  89. color[u] = 1;
  90.  
  91. for(set<int> :: iterator it = parent[u].begin(); it != parent[u].end(); it++) {
  92. int v = *it;
  93. if(color[v] == 1) assert(0);
  94. int num = 0;
  95. if(color[v] == 2) num = mark_pa[v];
  96. else num = dfs(v, u);
  97. //if(num > maxi) maxi = num, x = v;
  98. ans = ans + num;
  99. }
  100. color[u] = 2;
  101. mark_pa[u] = ans;
  102. return ans;
  103. }
  104. void _dfs(int u) {
  105. ans_v.push_back(u);
  106. int maxi = -1, x = u;
  107. for(set<int> :: iterator it = parent[u].begin(); it != parent[u].end(); it++) {
  108. int v = *it;
  109. if(mark_pa[v] > maxi) maxi = mark_pa[v], x = v;
  110. }
  111. if(maxi > 0) _dfs(x);
  112. }
  113. void solve() {
  114. int u, v; ll c; ss.clear();ans_v.clear(); cnt = 0;
  115. scanf("%d %d", &n, &m);
  116. for(int i = 0; i < n; i++) color[i] = 0, mark_pa[i] = 0;
  117. for(int i = 0; i < n; i++) graf[i].adj.clear(), graf[i].weight.clear();
  118. for(int i = 0; i < m; i++) {
  119. scanf("%d %d %lld", &u, &v, &c); --u, --v;
  120. graf[u].adj.push_back(v); graf[v].adj.push_back(u);
  121. graf[u].weight.push_back(c); graf[v].weight.push_back(c);
  122. }
  123. int total; scanf("%d", &total);
  124. for(int i = 0; i < total; i++) scanf("%d", &S[i]);
  125. for(int i = 0; i < total; i++) ss.insert(--S[i]);
  126. Dijkstra(S[0]);
  127.  
  128. int start = S[0];
  129. for(int i = 0; i < total; i++) if(graf[S[i]].dist > graf[start].dist) start = S[i];
  130. Dijkstra(start);
  131.  
  132. int other = start;
  133. for(int i = 0; i < total; i++) if(graf[S[i]].dist > graf[other].dist) other = S[i];
  134. /*cout << start << " " << other << endl;
  135.   for(int i = 0; i < n; i++) cout << graf[i].dist << " "; cout << endl;
  136.   cout << "set: ";
  137.   for(set<int> :: iterator it = ss.begin(); it != ss.end(); it++) {
  138.   cout << " " << *it;
  139.   } cout << endl;
  140.  
  141.   for(int i = 0; i < n; i++) {
  142.   cout << "parent of " << i << ": ";
  143.   for(set<int> :: iterator it = parent[i].begin(); it != parent[i].end(); it++) {
  144.   cout << (*it) << " ";
  145.   }
  146.   cout << endl;
  147.   }*/
  148.  
  149. dfs(other, other);
  150. //return;
  151. _dfs(other);
  152. int siz = ans_v.size();
  153. printf("%d\n", siz);
  154. assert((other == ans_v[0]) && (start == ans_v[siz - 1]));
  155. for(int i = 0; i < siz; i++) printf("%d ", ans_v[i] + 1); printf("\n");
  156.  
  157. //for(int i = 0; i < n; i++) cout << graf[i].dist << " "; cout << endl;
  158.  
  159. }
  160. int main() {
  161. int t = 1; scanf("%d", &t);
  162. for(int i = 0; i < t; i++) {
  163. //if(i == 1) assert(0);
  164. solve();
  165. }
  166. }
  167.  
Success #stdin #stdout 0s 16352KB
stdin
2
6 6
1 2 1
2 3 1
3 6 1
1 4 1
4 5 1
5 6 1
2
1 6
7 8
1 2 5
2 4 10
2 3 4
3 4 4
4 7 5
1 5 10
5 6 10
6 7 10
3
1 7 3
stdout
4
1 2 3 6 
5
1 2 3 4 7