fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ff first
  4. #define ss second
  5. #define pb push_back
  6. #define mp make_pair
  7.  
  8. #define MOD 1000000007
  9.  
  10. typedef long long ll;
  11. typedef long double ld;
  12.  
  13. const int INF=(int)(1e9);
  14. const ll INF64=(ll)(1e18);
  15. const ld EPS=1e-9;
  16. const ld PI=3.1415926535897932384626433832795;
  17.  
  18. const int N=100005;
  19.  
  20. vector<list<pair<int,int> > >adjList(N+1);    // Always give size of adjList
  21. list<pair<int,int> >::iterator it;
  22. int parent[N+1];
  23. int level[N+1];
  24. priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq; // priority queue    //Contains vertex and its distance
  25.  
  26. //  greater<pair<int,int> > is used to change std::priority queue to min heap
  27.  
  28. pair<int,int>p;    
  29.  
  30. int d[N+1];    //  distances from starting point
  31.  
  32. int n,m;
  33.  
  34. void dijkstra(int start){
  35.  
  36.     for(int i=1;i<=n;++i)
  37.         d[i]=INF;
  38.  
  39.     d[start]=0; 
  40.     // Preparing my priority queue
  41.     for(int i=1;i<=n;++i){
  42.  
  43.        pq.push(mp(d[i],i));
  44.     }
  45.  
  46.     int u,v,w;    
  47.     int count=n;
  48.  
  49.     while(count--){
  50.  
  51.         int u=pq.top().ss;   //  get value of element ,leave its weight 
  52.         pq.pop();
  53.  
  54.         it=adjList[u].begin();
  55.  
  56.         while(it!=adjList[u].end()){
  57.  
  58.              int v=it->ff;
  59.              int w=it->ss;
  60.  
  61.              if(d[u]+w<d[v]){
  62.  
  63.                 d[v]=d[u]+w;
  64.                 pq.push(mp(d[v],v));
  65.  
  66.              } 
  67.              ++it;
  68.          }
  69.  
  70.     }
  71.  
  72. }
  73.  
  74. int main(){
  75.  
  76.      int v1,v2,w;
  77.  
  78.      scanf("%d %d",&n,&m);
  79.  
  80.      for(int i=1;i<=m;++i){
  81.  
  82.            scanf("%d %d %d",&v1,&v2,&w);   
  83.            adjList[v1].pb(mp(v2,w));    
  84.      }
  85.  
  86.      dijkstra(1);  // start vertex goes in dijkstra
  87.  
  88.      for(int i=1;i<=n;++i)
  89.          printf("%d\n",d[i]);
  90.  
  91.      return 0;
  92. }
  93.  
Success #stdin #stdout 0s 4632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ugfGvV
language:
C++ (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!