fork(1) 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 <pair <ll,ll> > q;
  31.     q.insert({0,0});
  32.     while(!q.empty()){
  33.         pair <ll,ll> f=*q.begin(); q.erase(q.begin());
  34.         ll e=f.second;
  35.         for(auto x : vec[e]){
  36.             ll to=x.first; ll len=x.second;
  37.             if(d[e]+len<d[to]){
  38.                 q.erase({d[to],to});
  39.                 d[to]=d[e]+len;
  40.                 q.insert({d[to],to});
  41.             }
  42.         }
  43.     }
  44.     fr(i,n) cout<<d[i]<<" ";
  45.     cout<<endl;
  46.     return 0;
  47. }
Success #stdin #stdout 0s 6200KB
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/zKPhEZ
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!