fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int SIZE = 100;
  4.  
  5. vector < pair < int , int > > v [SIZE];  
  6. int dist [SIZE];
  7. bool vis [SIZE];
  8. int V,E;
  9.  
  10. void dijkstra(){
  11.  
  12.     // set the vertices distances as infinity
  13.     for(int i=0;i< SIZE; i++)
  14.         dist[i]=1e9;
  15.  
  16.     // set all vertex as unvisited
  17.     memset(vis, false , sizeof vis);    
  18.  
  19.     // source distance to itself equals to 0
  20.     dist[1] = 0;
  21.  
  22.     // priority_queue to do the job
  23.     priority_queue < pair < int , int >,vector<pair<int,int>>,greater<pair<int,int>> > pq; 
  24.  
  25.     // insert the source node with distance 0
  26.     pq.push({0 , 1});                         
  27.  
  28.     while(!pq.empty()){
  29.  
  30.         pair <int , int> p = pq.top();        // pop the vertex with the minimum          distance
  31.         pq.pop();
  32.  
  33.         int x = p.second;                       // x is the current vertex
  34.  
  35.         if( vis[x] )                            // check if the popped vertex is
  36.             continue;                           // visited before
  37.  
  38.         vis[x] = true;                           
  39.  
  40.         for(int i = 0; i < v[x].size(); i++){
  41.             int e = v[x][i].first; int w = v[x][i].second;
  42.             if(dist[x] + w < dist[e]  ){            // check if the next vertex             distance could be minimized
  43.                 dist[e] = dist[x] + w;
  44.                 pq.push({dist[e],  e} );           // insert the next vertex               with the updated distance
  45.             }
  46.         }
  47.     }
  48.     for(int i=1;i<=V;i++)
  49.         cout<<dist[i]<<" ";
  50. }
  51.  
  52. int main(){
  53.  
  54.     cin>>V>>E;
  55.     for(int i=0;i<E;i++){
  56.         int x,y,weight ;
  57.         cin>>x>>y>>weight ;
  58.         v[x].push_back({y,weight}) ;
  59.     }
  60.     dijkstra();
  61.  
  62.     return 0;
  63. }
Success #stdin #stdout 0s 4424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yHu8Hq
language:
C++14 (gcc 8.3)
created:
4 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!