fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define make(type,x) type x; cin>>x
  4. #define make2(type,x,y) type x,y; cin>>x>>y
  5. #define fr(x,y) for(long long x=0;x<y;x++)
  6. #define INF (ll) 1e18
  7.  
  8. # define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)
  9.  
  10. using namespace std;
  11.  
  12. ll n,m;
  13. ll N=1e5+5;
  14. vector <vector <pair <ll,ll> > >vec(N);
  15. vector <ll> d(N,INF);
  16. struct comp{
  17.     bool operator() (const ll &a, const ll &b) const{
  18.         return d[a]<=d[b];
  19.     }
  20.  
  21. };
  22. int main(){
  23.     IOS;
  24.     cin>>n>>m;
  25.     fr(i,m){
  26.         make2(ll,x,y); make(ll,len);
  27.         vec[--x].push_back({--y,len});
  28.     }
  29.     d[0]=0;
  30.     set <ll,comp> q;
  31.     q.insert(0);
  32.     while(!q.empty()){
  33.         ll e=*q.begin(); q.erase(q.begin());
  34.         for(auto x : vec[e]){
  35.             ll to=x.first; ll len=x.second;
  36.             if(d[e]+len<d[to]){
  37.                 q.erase(to);
  38.                 d[to]=d[e]+len;
  39.                 q.insert(to);
  40.             }
  41.         }
  42.     }
  43.     fr(i,n) cout<<d[i]<<" ";
  44.     cout<<endl;
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 6212KB
comments (?)
stdin
copy 
3 4
1 2 6
1 3 2
3 2 3
1 3 4
stdout
copy 
0 5 2
https://ideone.com/CMb3T5
language:
C++14 (gcc 8.3)
created:
4 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!