fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll           long long
  5. #define pii          pair<ll,ll>
  6. #define bug(a)       cerr << #a << " : " << a << endl;
  7. #define FastRead     ios_base::sync_with_stdio(false);cin.tie(NULL);
  8.  
  9. const int MAX = 3e6+10;
  10.  
  11. vector<pii>adj[MAX],newG[MAX];
  12. map<pii,int>vis;
  13. int node;
  14. ll dist[MAX];
  15.  
  16. struct Info
  17. {
  18.     ll d;
  19.     int u,x;
  20.  
  21.     Info(){}
  22.     Info(ll _d,int _u,int _x)
  23.     {
  24.         d = _d;
  25.         u = _u;
  26.         x = _x;
  27.     }
  28. };
  29. bool operator<(const Info &x,const Info &y)
  30. {
  31.     return x.d >= y.d;
  32. }
  33. bool endd[MAX];
  34. int en;
  35. void DFS(int src,int x,int par)
  36. {
  37.     if(src == en)
  38.         endd[node] = 1;
  39.     vis[{src,x}] = node++;
  40.     int u = vis[{src,x}];
  41.     //cout << src << " " << x << " " << par << endl;
  42.     for(int j=0;j<adj[src].size();j++)
  43.     {
  44.         int v = adj[src][j].first , w = adj[src][j].second;
  45.         int newX = __gcd(x,w);
  46.  
  47.         if(x >= w)
  48.         {
  49.             if(!vis[{v,newX}] && v != par)
  50.             {
  51.                 DFS(v,newX,u);
  52.                 v = vis[{v,newX}];
  53.                 newG[u].push_back({v,w});
  54.                 newG[v].push_back({u,w});
  55.             }
  56. //            else if(v != par)
  57. //            {
  58. //                v = vis[{v,newX}];
  59. //                newG[u].push_back({v,w});
  60. //                newG[v].push_back({u,w});
  61. //            }
  62.         }
  63.     }
  64. }
  65. ll dijkstra(int src,int en,int x)
  66. {
  67.     priority_queue< Info > pq;
  68.     fill(dist,dist+MAX,1e18);
  69.  
  70.     pq.push({0,src,x});
  71.     dist[src] = 0;
  72.  
  73.     while(pq.size())
  74.     {
  75.         int u = pq.top().u;
  76.         ll d = pq.top().d;
  77.         pq.pop();
  78.         //cout << u << " >>> " << d << endl;
  79.         if(endd[u])
  80.             return d;
  81.  
  82.         for(int j=0;j<newG[u].size();j++)
  83.         {
  84.             int v = newG[u][j].first , w = newG[u][j].second;
  85.  
  86.             if(dist[v] > dist[u]+w)
  87.             {
  88.                 dist[v] = dist[u]+w;
  89.                 pq.push({dist[v],v,__gcd(x,w)});
  90.             }
  91.         }
  92.     }
  93.     return 1e18;
  94. }
  95. int main()
  96. {
  97.     FastRead
  98.  
  99.     int t,cas=1;
  100.  
  101.     cin >> t;
  102.  
  103.     while(t--)
  104.     {
  105.         int n,m,x,y,w;
  106.  
  107.         cin >> n >> m;
  108.  
  109.         for(int i=1;i<=n;i++)
  110.             adj[i].clear() , newG[i].clear();
  111.  
  112.         while(m--)
  113.         {
  114.             cin >> x >> y >> w;
  115.             adj[x].push_back({y,w});
  116.             adj[y].push_back({x,w});
  117.         }
  118.  
  119.         vis.clear();
  120.         memset(endd,0,sizeof endd);
  121.         node = 1;
  122.         int st;
  123.  
  124.         cin >> st >> en >> x;
  125.  
  126.         DFS(st,x,-1);
  127.  
  128.  
  129.         ll res = dijkstra(vis[{st,x}],en,x);
  130.  
  131.         if(res < 1e18)
  132.             cout << "Case " << cas++ << ": " << res << endl;
  133.         else
  134.             cout << "Case " << cas++ << ": impossible" << endl;
  135.     }
  136. }
  137.  
Runtime error #stdin #stdout 0.04s 143776KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/sKnRzJ
language:
C++14 (gcc 8.3)
created:
5 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!