fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define endl '\n'
  7.  
  8. const int maxN = 1e6+12;
  9. const int MOD = 1e9+7;
  10. const ll inf = 1e18;
  11.  
  12. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  13. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  14.  
  15. int n, m;
  16. ll d[maxN];
  17. bool mark[maxN];
  18. vector<pair<ll,ll>> g[maxN];
  19.  
  20. void dijkstra(int s)
  21. {
  22.     d[s]=0;
  23.     priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
  24.  
  25.     pq.push({0,s});
  26.  
  27.     while(!pq.empty()){
  28.         ll u = pq.top().second;
  29.         pq.pop();
  30.  
  31.         if(!mark[u]){
  32.             mark[u]=1;
  33.             for(auto v: g[u]){
  34.                 ll x = v.first;
  35.                 ll y = v.second;
  36.  
  37.                 if(d[x] > d[u]+y){
  38.                     d[x] = d[u]+y;
  39.                     pq.push({d[x],x});
  40.                 }
  41.             }
  42.         }
  43.     }
  44. }
  45.  
  46. int main()
  47. {
  48.     ios_base::sync_with_stdio(0);
  49.     cin.tie(0);
  50.     cout.tie(0);
  51.  
  52.     if(fopen("a.inp", "r")){
  53.         freopen("a.inp", "r", stdin);
  54.         freopen("a.out", "w", stdout);
  55.     }
  56.  
  57.     cin >> n >> m;
  58.     for(int i=1; i<=m; i++){
  59.         int a, b, c;
  60.         cin >> a >> b >> c;
  61.         g[a].push_back({b,c});
  62.     }
  63.  
  64.     fill_n(mark, n+1, 0);
  65.     fill_n(d, n+1, inf);
  66.  
  67.     dijkstra(1);
  68.  
  69.     for(int i=1; i<=n; i++) cout << d[i] << " ";
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 28096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ww2qzK
language:
C++ (gcc 8.3)
created:
6 days 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!