fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define N 100010
  3. using namespace std;
  4. typedef pair<int,int> pi;
  5. vector<pi> a[N];
  6. int oo=1e9+7;
  7. int dis[N];
  8. int trace[N];
  9. int n,m;
  10. void dijkstra()
  11. {
  12.     priority_queue<pi,vector<pi>,greater<pi> >pq;
  13.     for(int i=1;i<=n;i++)
  14.         dis[i]=1000000007;
  15.     dis[1]=0;
  16.     pq.push(pi(0,1));
  17.     while(pq.size())
  18.     {
  19.         int u,du,w,v;
  20.         u=pq.top().second;
  21.         du=pq.top().first;
  22.         pq.pop();
  23.        // cout<<u<<"\n";
  24.         if(du!=dis[u]) continue;
  25.         // Because you may be push into priority queue vertex u a few times so this guaranteed this is the shortest path from 1 to u at this time
  26.         for(int i=0;i<a[u].size();i++)
  27.         {
  28.             v=a[u][i].second;
  29.             w=a[u][i].first;
  30.             //cout<<v<<" "<<dis[v]<<" "<<du+w<<"\n";
  31.             if(du+w<dis[v])
  32.             {
  33.                 dis[v]=du+w;
  34.                 trace[v]=u;
  35.                 pq.push(pi(dis[v],v));
  36.             }
  37.         }
  38.         //cout<<u<<"\n";
  39.     }
  40. }
  41. void _trace(int x)
  42. {
  43.     printf("%d ",x);
  44.     if(x==1)
  45.         return;
  46.     _trace(trace[x]);
  47. }
  48. int main()
  49. {
  50.     scanf("%d %d",&n,&m);
  51.     for(int i=1;i<=m;i++)
  52.     {
  53.         int x,y,w;
  54.         scanf("%d %d %d",&x,&y,&w);
  55.         a[x].push_back(pi(w,y));
  56.         a[y].push_back(pi(w,x));
  57.     }
  58.    // cout<<a[1].size()<<"\n";
  59.     dijkstra();
  60.     for(int i=1;i<=n;i++)
  61.     {
  62.         if(dis[i]!=oo)
  63.         {
  64.         printf("The shortest path from 1 to %d is: %d\n",i,dis[i]);
  65.         printf("And this is the shortest path from %d to 1: ",i);
  66.         _trace(i);
  67.         printf("\n");
  68.         }
  69.         else
  70.         {
  71.         printf("There is no shortest path from 1 to %d\n",i);
  72.         }
  73.  
  74.     }
  75. }
  76.  
  77.  
Success #stdin #stdout 0s 18368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cjUnQ3
language:
C++14 (gcc 8.3)
created:
8 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!