fork(2) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
4
1 2 3 6 
5
1 2 3 4 7
https://ideone.com/JWhnNH
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years ago
visibility:
secret

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!