fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define ld long double
  7. #define eb emplace_back
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define nn '\n'
  12. #define pi pair<int, int>
  13. #define unmp unordered_map
  14. #define uns unordered_set
  15. #define lb lower_bound
  16. #define ub upper_bound
  17. #define pq priority_queue
  18. #define TASK " "
  19.  
  20. const int INF = 1e18;
  21. const int mod = 1e9+7;
  22. const int N = 1e5 + 5;
  23. int MOD = 998244353;
  24. int bit[200000];
  25. int n, m;
  26. vector<pair<int, int>> adj[N];
  27. int a[5];
  28. int kq = -INF;
  29. void nhap(){
  30.     cin >> n;
  31.     for(int i = 1; i <= 4; i++){
  32.         cin >> a[i];
  33.     }
  34.     int x, y, w;
  35.     while(cin >> x >> y >> w){
  36.         adj[x].eb( y, w );
  37.         adj[y].eb( x, w );
  38.     }
  39. }
  40. void dijkstra(int s){
  41.     vector<int> d(n + 1, INF);
  42.     d[s] = 0;
  43.     priority_queue<pi, vector<pi> , greater<pi>> q;
  44.     q.push({0, s});
  45.     while(!q.empty()){
  46.         pair<int, int> top = q.top(); q.pop();
  47.         int  u = top.second;
  48.         int kc = top.first;
  49.         if(kc > d[u]) continue;
  50.  
  51.         for( auto it : adj[u]){
  52.             int v = it.first;
  53.             int w = it.second;
  54.  
  55.             if (d[v] > d[u] + w) {
  56.                  d[v] = d[u] + w;
  57.                  q.push({d[v], v});
  58.             }
  59.         }
  60.  
  61.     }
  62.     for(int i =	1 ; i <= 4; i++){
  63.         // kq = max(kq, d[a[i]]);
  64.         cout << d[ a[i] ] << " ";
  65.     }
  66.     // cout << kq << nn;
  67. }
  68. signed main(){
  69.     ios_base::sync_with_stdio(0);
  70.     cin.tie(0);
  71.     cout.tie(0);
  72.     nhap();
  73.     dijkstra(a[1]);
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0.01s 6904KB
comments (?)
stdin
copy 
5
2 3 4 1
1 2 10
1 5 1
5 2 1
1 4 1
4 3 3
3 2 2
stdout
copy 
0 2 3 2
https://ideone.com/R5xf9y
language:
C++14 (gcc 8.3)
created:
15 hours 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!