fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define el '\n'
  4. #define fi first
  5. #define sec second
  6. #define pb push_back
  7. #define ll long long
  8. #define pii pair<int,int>
  9. #define sz(v) (int)(v).size()
  10. #define all(v) (v).begin(),(v).end()
  11. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  12. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  13.  
  14. using namespace std;
  15.  
  16. const long long LLNF = 0x3f3f3f3f3f3f3f3f;
  17. const int MAX_N = 44444;
  18.  
  19. struct Huyen_Tram{
  20.     ll len;
  21.     int nho, type, u;
  22. };
  23.  
  24. struct cmp{
  25.     bool operator()(const Huyen_Tram &x, const Huyen_Tram &y){
  26.         return x.len > y.len;
  27.     }
  28. };
  29.  
  30. vector<pii> g[MAX_N + 5];
  31. ll dist[MAX_N + 5][5][200];
  32. int n, m, k;
  33.  
  34. void Input(){
  35.     cin >> n >> m >> k;
  36.     FOR(i, 1, m){
  37.         int u, v, w;
  38.         cin >> u >> v >> w;
  39.         g[u].pb({v, w});
  40.         g[v].pb({u, w});
  41.     }
  42. }
  43.  
  44. inline ll power(ll x){
  45.     ll res = 1;
  46.     FOR(i, 1, k) res *= x;
  47.     return res;
  48. }
  49.  
  50. void dijk(){
  51.     memset(dist, 0x3f, sizeof(dist));
  52.     priority_queue<Huyen_Tram, vector<Huyen_Tram>, cmp> pq;
  53.  
  54.     pq.push({0, 0, 0, 1});
  55.     dist[1][0][0] = 0;
  56.  
  57.     while(sz(pq)){
  58.         int u = pq.top().u;
  59.         int type = pq.top().type;
  60.         int nho = pq.top().nho;
  61.         ll len = pq.top().len;
  62.         pq.pop();
  63.  
  64.         if(len > dist[u][type][nho]) continue;
  65.  
  66.         for(pii x : g[u]){
  67.             int v = x.fi, w = x.sec;
  68.  
  69.             int next_type = (type + 1) % k;
  70.             int next_nho = (next_type == 0 ? 0 : nho + w);
  71.             ll add = (next_type == 0 ? power(nho + w) : 0);
  72.  
  73.             if(dist[v][next_type][next_nho] > len + add){
  74.                 dist[v][next_type][next_nho] = len + add;
  75.                 pq.push({dist[v][next_type][next_nho], next_nho, next_type, v});
  76.             }
  77.         }
  78.     }
  79. }
  80.  
  81. void Solve(){
  82.     dijk();
  83.     FOR(i, 1, n){
  84.         if(dist[i][0][0] != LLNF) cout << dist[i][0][0] << " ";
  85.         else cout << -1 << " ";
  86.     }
  87. }
  88.  
  89. int main(){
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0);
  92.  
  93.     Input();
  94.     Solve();
  95. }
  96.  
Success #stdin #stdout 0.12s 351808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NFs6kn
language:
C++14 (gcc 8.3)
created:
4 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!