fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // #include <ext/pb_ds/assoc_container.hpp>
  5. // #include <ext/pb_ds/tree_policy.hpp>
  6. // using namespace __gnu_pbds;
  7. // #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  8.  
  9. #define ff              first
  10. #define ss              second
  11. #define fo(i,n)         for(int i=0;i<n;i++)
  12. #define fod(i,n)        for(int i=n-1;i>=0;i--)
  13. #define For(i,a,b)      for(int i=a;i<=b;i++)
  14. #define all(x)          x.begin(),x.end()
  15. #define SET(x,v)        memset(x,v,sizeof(x))
  16. #define si              set<int>
  17. #define pb(i)           push_back(i)
  18. #define sll             set<long long>
  19. #define vs              vector<string>
  20. #define yes             cout<<"YES\n"
  21. #define no              cout<<"NO\n"
  22. #define vpii            vector<pair<int,int>>
  23. #define ll              long long int
  24. #define vi              vector<ll>
  25. #define mod             1000000007
  26. #define tc(t)           int t; cin>>t; while(t--)
  27. #define sfm(a,m,n)      ll a[m][n]; fo(i,m) fo(j,n) cin>>a[i][j]
  28. #define sfarr(a,n)      ll a[n]; fo(i,n) cin>>a[i]
  29. #define sfv(v,n)        vi v(n); for(ll &i:v) cin>>i
  30. // int f[1000001];
  31. // int prime[1000001];
  32. // void sieve(){
  33. //     prime[0]=prime[1]=0;
  34. //     For(i,2,1000000) prime[i]=1;
  35. //     for(int i=2;i*i<=1000000;i++){
  36. //         if(prime[i]){
  37. //             for(ll j=i*i;j<=1000000;j+=i)
  38. //             prime[j]=0;
  39. //         }
  40. //     }
  41. // }
  42. // int power(int a,int b){
  43. //     int r=1;
  44. //     while(b){
  45. //         if(b&1){
  46. //             r=(r*1ll*a)%mod;
  47. //             b--;
  48. //         }
  49. //         else{
  50. //             a=(a*1ll*a)%mod;
  51. //             b>>=1;
  52. //         }
  53. //     }
  54. //     return r;
  55. // }
  56. // void factorial(){
  57. //     f[0]=f[1]=1;
  58. //     For(i,2,1000000) f[i]=(f[i-1]*1ll*i)%mod;
  59. // }
  60. // int nCr(int a,int b){
  61. //     if(b>a) return 0;
  62. //      factorial();
  63. //      int r=f[a]; 
  64. //      r=(r*1ll*power(f[b],mod-2))%mod;
  65. //      r=(r*1ll*power(f[a-b],mod-2))%mod;
  66. //      return r;
  67. // }
  68. // vi z_algo(string s){
  69. //     ll n=s.length(),l=0,r=0;
  70. //     vi z(n);
  71. //     For(i,1,n-1){
  72. //         if(i<=r) z[i]=min(r-i+1,z[i-l]);
  73. //         while(z[i]+i<n && s[z[i]]==s[i+z[i]]) z[i]++;
  74. //         if(i+z[i]-1>r) l=i,r=i+z[i]-1;
  75. //     }
  76. //     return z;
  77. // }
  78. // int parent[1000001];
  79. // int ranker[1000001];
  80. // int findpar(int node){
  81. //     if(node==parent[node])
  82. //     return node;
  83. //     return parent[node]=findpar(parent[node]);
  84. // }
  85. // void connect(int u,int v){
  86. //     u=findpar(u);
  87. //     v=findpar(v);
  88. //     if(u==v) return;
  89. //     if(ranker[u]<ranker[v])
  90. //     parent[u]=v;
  91. //     else if(ranker[u]>ranker[v])
  92. //     parent[v]=u;
  93. //     else{
  94. //         parent[v]=u;
  95. //         ranker[u]++;
  96. //     }
  97. // }
  98. vector<bool> vis(1000001,0);
  99. vector<int> g[1000001];
  100. // void graph(vector<int> g[],int e,bool t){
  101. //     fo(i,e){
  102. //         int u,v; cin>>u>>v;
  103. //         g[u].pb(v);
  104. //         if(!t)
  105. //         g[v].pb(u);
  106. //     }
  107. // }
  108. // void dfs(int node){
  109. //     vis[node]=1;
  110. //     for(int child:g[node]){
  111. //         if(!vis[child])
  112. //         dfs(child);
  113. //     }
  114. // }
  115. // priority_queue <int, vector<int>, greater<int>> g;
  116. signed main(){
  117.     ios_base::sync_with_stdio(false);
  118.     cin.tie(NULL);
  119.     int n,m; cin>>n>>m;
  120.     priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> hp;
  121.     vi dist(n+1,1e18);
  122.     vector<pair<ll,ll>> g[1000001];
  123.     fo(i,m){
  124.         ll a,b,c; cin>>a>>b>>c;
  125.         g[a].pb(make_pair(c,b));
  126.     }
  127.     hp.push({0,1});
  128.     dist[1]=0;
  129.     while(hp.size()){
  130.         pair<int,int> pq=hp.top();
  131.         int wt=hp.top().ff,node=hp.top().ss;
  132.         hp.pop();
  133.         if(vis[pq.ss]) continue;
  134.         else vis[pq.ss]=1;
  135.         for(auto child:g[node]){
  136.             if(dist[node]+wt<dist[child.ss]){
  137.                 dist[child.ss]=dist[node]+wt;
  138.                 hp.push({child.ff,child.ss});
  139.             }
  140.         }
  141.     }
  142.     For(i,1,n) cout<<dist[i]<<" ";
  143. return 0;
  144. }
  145.  
  146.  
Success #stdin #stdout 0.01s 50548KB
comments (?)
stdin
copy 
3 4
1 2 6
1 3 2
3 2 3
1 3 4
stdout
copy 
0 0 0
https://ideone.com/76KDZS
language:
C++14 (gcc 8.3)
created:
2 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!