fork(2) download
  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
stdin
3 4
1 2 6
1 3 2
3 2 3
1 3 4
stdout
0 5 2