fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<fstream>
  3. using namespace std;
  4. #define sz(a) (int)a.size()
  5. #define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
  6. #define ll long long
  7. #define int long long
  8. #define pb push_back
  9. #define forr(i, a, b) for(int i = a; i < b; i++)
  10. #define dorr(i, a, b) for(int i = a; i >= b; i--)
  11. #define ld long double
  12. #define vt vector
  13. #include<fstream>
  14. #define fi first
  15. #define se second
  16. #define pll pair<ll, ll>
  17. #define pii pair<int, int>
  18. const ld PI = 3.14159265359;
  19. const ll mod = 998244353;
  20. const int mxn = 3e5 + 5, mxm = 1e5;
  21. int n, m, d;
  22. ll dis[mxn + 1], a[mxn + 1], x[mxn + 1];
  23. int up[mxn + 1][20], in[mxn + 1];
  24. vt<pii>adj[mxn + 1];
  25. vt<int>g[mxn + 1];
  26. pii dp[mxn + 1];
  27. void ckmin(pii &a, pii b){
  28.     if(b.fi < a.fi)a = b;
  29.     else if(a.fi == b.fi){
  30.         if(b.se > a.se)a = b;
  31.     }
  32. }
  33. int get(int l, int r){
  34.     int lg = __lg(r - l + 1);
  35.     return(max(up[l][lg], up[r - (1 << lg) + 1][lg]));
  36. }
  37. signed main(){
  38.  
  39.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  40.     cin >> n >> m;
  41.     forr(i, 0, m){
  42.         int u, v, w; cin >> u >> v >> w;
  43.         adj[u].pb({v, w}); adj[v].pb({u, w});
  44.     }
  45.     for(int i = 1; i <= n; i++)dis[i] = 1e18;
  46.     priority_queue<pll, vt<pll>, greater<pll>>pq;
  47.     int k; cin >> k;
  48.     forr(i, 0, k){
  49.         cin >> a[i]; dis[a[i]] = 0; pq.push({dis[a[i]], a[i]});
  50.     }
  51.    cin >> d;
  52.     for(int i = 1; i <= d; i++){
  53.         cin >> x[i]; up[i][0] = x[i];
  54.     }
  55.     for(int i = 1; i < 20; i++){
  56.         for(int j = 1; j + (1 << i) - 1 <= d; j++){
  57.             up[j][i] = max(up[j][i - 1], up[j + (1 << (i - 1))][i - 1]);
  58.         }
  59.     }
  60.     while(!pq.empty()){
  61.  
  62.         auto [dd, u] = pq.top(); pq.pop();
  63.         if(dis[u] != dd)continue;
  64.         for(auto [v, w]: adj[u]){
  65.             if(dis[v] > dis[u] + w){
  66.                 dis[v] = dis[u] + w; 
  67.                 pq.push({dis[v], v});
  68.             }
  69.         }
  70.     }
  71.     for(int i = 1; i <= n; i++){
  72.         //cout << dis[i] << " ";
  73.         for(auto [v, w]: adj[i]){
  74.             if(dis[i] + w == dis[v]){
  75.                 g[i].pb(v); in[v]++;
  76.             }
  77.         }
  78.     }
  79.     for(int i = 1; i <= n; i++){
  80.         dp[i] = make_pair(1e9, 0);
  81.     }
  82.     queue<int>q;
  83.     for(int i = 1; i <= n; i++){
  84.         if(in[i] == 0 && dis[i] < 1e18){
  85.             dp[i] = make_pair(0, 0);
  86.             q.push(i);
  87.         }
  88.     }
  89.  
  90.     while(!q.empty()){
  91.         int nw = q.front(); q.pop();
  92.  
  93.         for(auto i: g[nw]){
  94.             ll need = dis[i] - dis[nw];
  95.  
  96.             if(dp[nw].se >= need && dp[nw].fi != 1e9){
  97.                 ckmin(dp[i], make_pair(dp[nw].fi, dp[nw].se - need));
  98.             }
  99.                 int l = dp[nw].fi + 1, r = d, ans = -1, val = -1;
  100.                 while(l <= r){
  101.                     int mid = (l + r) >> 1;
  102.                     ll cand = get(dp[nw].fi + 1, mid);
  103.                     if(cand >= need){
  104.                         ans = mid; r = mid - 1; val = cand;
  105.                     }else{
  106.                         l = mid + 1;
  107.                     }
  108.                 }
  109.                 if(ans != -1){
  110.  
  111.                     ckmin(dp[i], make_pair(ans, val - need));
  112.                 }
  113.  
  114.  
  115.             in[i]--;
  116.             if(in[i] == 0){
  117.                 q.push(i);
  118.             }
  119.  
  120.     }
  121.     }
  122.     for(int i = 1; i <= n; i++){
  123.         cout << ((dp[i].fi >= 1e9) ? -1 : dp[i].fi) << "\n";
  124.     }
  125.     return(0);
  126. }
Runtime error #stdin #stdout 0.04s 34860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/N6Y2xR
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!