fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define pb push_back
  6. #define fi first
  7. #define se second
  8. #define nn '\n'
  9. #define pi pair<ll,ll>
  10. #define unmp unordered_map
  11. #define uns unordered_set
  12. ll mod = 1e9+7;
  13. const int N = 2*1e5 + 5 ;
  14. int bit[200000];
  15. int n, m;
  16. vector<pair<int, int>> adj[N];
  17. const int INF = 1e9;
  18. void nhap(){
  19.     cin >> n >> m;
  20.     for( int i = 1 ; i <= m; i++){
  21.         int x, y , w;
  22.         cin >> x >> y >> w;
  23.         adj[x].push_back({y, w});
  24.     }
  25. }
  26. void dijkstra(int s){
  27.     s = 1;
  28.     vector<ll> d(n + 1, INF);
  29.     d[1] = 0;
  30.     priority_queue<pair<int, int>, vector<pair<int, int>> , greater<pair<int,int>>> q;
  31.     q.push({0, s});
  32.     while(!q.empty()){
  33.         pair<int, int> top = q.top(); q.pop();
  34.         int  u = top.second;
  35.         int kc = top.first;
  36.         if(kc > d[u]) continue;
  37.  
  38.         for( auto it : adj[u]){
  39.             int v = it.first;
  40.             int w = it.second;
  41.             d[v] = max(d[v], d[u] + w);
  42.             q.push({d[v], v});
  43.         }
  44.     }
  45.     for( int i =1; i<= n ;i++){
  46.         cout << d[i] << " ";
  47.     }
  48. }
  49. int main(){
  50.     ios_base::sync_with_stdio(0);
  51.     cin.tie(0);
  52.     cout.tie(0);
  53.     nhap();
  54.     dijkstra(1);
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 8280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zVZlZa
language:
C++14 (gcc 8.3)
created:
2 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!