fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define maxn 300005
  5. #define sti string
  6. #define int long long
  7.  
  8. using namespace std;
  9.  
  10. int val[maxn],Rank[maxn],test;
  11. vector<pair<int,int>> adj[maxn];
  12. bool vis[maxn];
  13. const int mod = 998244353;
  14.  
  15. struct node {
  16.   int idx,w,v,u;
  17. };
  18.  
  19. signed main()
  20. {
  21.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  22.     cin>>test;
  23.     while(test--){
  24.         int n,m,k;
  25.         cin>>n>>m>>k;
  26.         for(int i=1;i<=n;i++) {
  27.             adj[i].clear();
  28.             vis[i] = 0;
  29.             Rank[i] = 0;
  30.             val[i] = 0;
  31.         }
  32.         for(int i=1;i<=m;i++){
  33.             int u,v,w;
  34.             cin>>u>>v>>w;
  35.             adj[u].push_back({v,w});
  36.             adj[v].push_back({u,w});
  37.         }
  38.         vector<int> cur;
  39.         cur.push_back(1);
  40.         vis[1] = 1;
  41.         for(int u : cur){
  42.             for(auto [v,w] : adj[u]){
  43.                 if(w == 0 && !vis[v]){
  44.                     vis[v] = 1;
  45.                     cur.push_back(v);
  46.                 }
  47.             }
  48.         }
  49.         while(!cur.empty()){
  50.             vector<node> vec;
  51.             for(int u : cur){
  52.                 for(auto [v,w] : adj[u]){
  53.                     if(!vis[v]){
  54.                         vec.push_back({Rank[u],w,v,u});
  55.                     }
  56.                 }
  57.             }
  58.             sort(vec.begin(), vec.end(), [](const node& a, const node& b) {
  59.                 if (a.idx != b.idx) return a.idx < b.idx;
  60.                 return a.w < b.w;
  61.             });
  62.             vector<int> nxt;
  63.             int curidx = -1;
  64.             int lastidx = -1,lastW = -1;
  65.             for(auto [idx,w,v,u] : vec){
  66.                 if(vis[v]) continue;
  67.                 if(idx != lastidx || w != lastW){
  68.                     curidx++;
  69.                     lastidx = idx;
  70.                     lastW = w;
  71.                 }
  72.                 vis[v] = 1;
  73.                 Rank[v] = curidx;
  74.                 val[v] = ((val[u] * k % mod) + w)%mod;
  75.                 nxt.push_back(v);
  76.             }
  77.             cur = nxt;
  78.         }
  79.         for(int i=1;i<=n;i++) {
  80.             if(!vis[i]) cout<<-1<<' ';
  81.             else cout<<val[i]<<' ';
  82.         }
  83.         cout<<'\n';
  84.     }
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0.01s 10724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1wVQDU
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!