fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define inf 1e9
  3. using namespace std;
  4. ifstream fin("dijkstra.in");
  5. ofstream fout("dijkstra.out");
  6. vector < pair <int, int> > G[50005];
  7. set < pair <int, int> > s;
  8. int d[50005];
  9. bool viz[50005];
  10. void dijkstra(){
  11.     d[1] = 0;
  12.     s.insert({0,1});
  13.     while(!s.empty()){
  14.         set < pair <int, int> > :: iterator it = s.begin();
  15.         int nod = it->second;
  16.         s.erase(it);
  17.         if(viz[nod]) continue;
  18.         viz[nod] = 1;
  19.         for(int i = 0; i < G[nod].size(); ++i){
  20.             int c = G[nod][i].first;
  21.             int x = G[nod][i].second;
  22.             if(!viz[x] && d[nod] + c < d[x]){
  23.                 d[x] = d[nod] + c;
  24.                 s.insert({d[x],x});
  25.             }
  26.         }
  27.     }
  28. }
  29. int main()
  30. {
  31.     int n,m,i,u,v,c;
  32.     cin >> n >> m;
  33.     for(i = 1; i <= n; i++) d[i] = inf;
  34.     for(i = 1; i <= m; i++){
  35.         cin >> u >> v >> c;
  36.         G[u].push_back({c,v});
  37.     }
  38.     dijkstra();
  39.     for(i = 2; i <= n; i++) cout << (d[i] != inf ? d[i] : 0) << " ";
  40.     cout << "\n";
  41.     return 0;
  42. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 5 3
3 5 6
stdout
copy 
1 3 2 5
https://ideone.com/NCMV8S
Dijkstra s algorithm with Set Data Structure
language:
C++14 (gcc 8.3)
created:
258 days 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!