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 pb push_back
  8. #define eb emplace_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 TASK ""
  16.  
  17. const int INF = 1e9;
  18. int mod = 1e9+7;
  19. const int N = 1e5 + 5;
  20. int MOD = 998244353;
  21. int bit[200000];
  22. int n, m, k, s, t;
  23. int x[N];
  24. vector<pi> adj[N];
  25. int d[N][20];
  26. struct State{
  27.     int dist, u, used;
  28.     bool operator>(const State& other) const{
  29.         return dist > other.dist;
  30.     }
  31. };
  32.  
  33. void nhap(){
  34.     cin >> n >> m >> k;
  35.     for( int i = 1 ; i <= m; i++){
  36.         int x, y , w;
  37.         cin >> x >> y >> w;
  38.         adj[x].eb(y, w);
  39.         adj[y].eb( x, w );
  40.     }
  41. }
  42. void dijkstra(int s){
  43.     for(int i = 1; i <= n; i++){
  44.         for(int j = 0; j <= k; j++){
  45.             d[i][j] = INF;
  46.         }
  47.     }
  48.     d[s][k] = 0;
  49.     priority_queue<State, vector<State>, greater<State>> q;
  50.     q.push({d[s][k], s, k});
  51.     while(!q.empty()){
  52.         State cur = q.top(); q.pop();
  53.         int kc = cur.dist, u = cur.u, ud = cur.used;
  54.         if(kc > d[u][ud]) continue;
  55.  
  56.         for(auto [v, w] : adj[u]){
  57.             if(d[v][ud] > kc + w){
  58.                 d[v][ud] = kc + w;
  59.                 q.push({d[v][ud], v, ud});
  60.             }
  61.             if(ud > 0){
  62.                 if(d[v][ud - 1] > kc + 0){
  63.                     d[v][ud - 1] = kc ;
  64.                     q.push({d[v][ud - 1], v, ud - 1});
  65.                 }
  66.             }
  67.         }
  68.  
  69.     }
  70.     for(int j = 1; j <= n; j++){
  71.         int kq = INF;
  72.         for(int i = 0; i <= k; i++){
  73.             kq = min(kq, d[j][i]);
  74.         }
  75.         cout << kq << " ";
  76.     }
  77. }
  78. signed main(){
  79.     ios_base::sync_with_stdio(0);
  80. 	cin.tie(0);
  81. 	cout.tie(0);
  82.     if(fopen(TASK".INP","r")){
  83.         freopen(TASK".INP","r",stdin);
  84.         freopen(TASK".OUT","w",stdout);
  85.     }
  86.     nhap();
  87.     dijkstra(1);
  88. 	return 0;
  89. }
  90.  
Success #stdin #stdout 0.01s 7684KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rTxvSP
language:
C++14 (gcc 8.3)
created:
4 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!