Facebook
From emanlaicepsa, 1 Month ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 40
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define int ll
  5. #define fi first
  6. #define se second
  7. #define pb emplace_back
  8. #define all(n) (n).begin(),(n).end()
  9. #define mem(n,x) memset(n,x,sizeof(n))
  10. #define IOS ios::sync_with_stdio(0),cin.tie(0)
  11. #define pii pair<ll,ll>
  12. #define vi vector<ll>
  13. #define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
  14. template<typename A> void _do(A x){ cerr<<x<<"\n"; }
  15. template<typename A, typename ...B> void _do(A x, B ...y){ cerr<<x<<", "; _do(y...);}
  16.  
  17. ll n, p, s, m;
  18. vi d;
  19.  
  20. void dijkstra(vi &d, vector<vector<pii>> &E){
  21.         fill(all(d),1e9);
  22.         d[p+1] = 0;
  23.         priority_queue<pii, vector<pii>, greater<pii>> pq;
  24.         pq.emplace(0,p+1);
  25.         while(!pq.empty()){
  26.                 int dis, nd;
  27.                 tie(dis, nd) = pq.top(); pq.pop();
  28.                 //dbg(dis, nd);
  29.                 if(d[nd] < dis) continue;
  30.                 d[nd] = dis;
  31.                 for(auto &x:E[nd]){
  32.                         if(d[x.fi] > dis + x.se){
  33.                                 d[x.fi] = dis + x.se;
  34.                                 pq.emplace(d[x.fi], x.fi);
  35.                         }
  36.                 }
  37.         }
  38. }
  39.  
  40. inline ll cost(ll i,ll j){
  41.     return (d[j]-d[i]) * (j-i-1);
  42. }
  43.  
  44. pii dp[5005];
  45.  
  46. inline ll val(ll id,ll x){
  47.     return dp[id].fi + cost(id,x);
  48. }
  49.  
  50. pii aliens(ll m){
  51.     mem(dp, 0);
  52.     dp[0] = {0,0};
  53.     deque<pii> dq;
  54.     dq.pb(1,0);
  55.     for(int i=1;i<=p;i++){
  56.         while(dq.size()>=2 && dq[1].fi<=i) dq.pop_front();
  57.         dp[i] = {cost(dq[0].se, i) + dp[dq[0].se].fi + m, dp[dq[0].se].se + 1};
  58.         while(!dq.empty()){
  59.             if( i>=dq.back().fi || val(dq.back().se, dq.back().fi) <= val(i, dq.back().fi)) break;
  60.             dq.pop_back();
  61.         }
  62.         if(dq.empty()){
  63.             dq.pb(i+1,i);
  64.         }
  65.         else{
  66.             ll l = max(dq.back().fi,i+1), r = p+1, lid = dq.back().se;
  67.             while(l<r){
  68.                 ll m = (l+r)/2;
  69.                 if(val(lid,m) <= val(i,m)) l = m+1;
  70.                 else r=m;
  71.             }
  72.             if(l<=p)dq.pb(l,i);
  73.         }
  74. //        cout<<"dq = \n";
  75. //        for(auto i:dq) cout<<i.fi<<", "<<i.se<<" \n";
  76. //        cout<<'\n';
  77.     }
  78.     return dp[p];
  79. }
  80.  
  81.  
  82. signed main(){
  83.         IOS;
  84.     cin>>n>>p>>s>>m;
  85.         vi d1(n+10), d2(n+10);
  86.         d.resize(n+10);
  87.         vector<vector<pii>> E1(n+10), E2(n+10);
  88.  
  89.         for(int i=1,s,t,v;i<=m;i++){
  90.                 cin>>s>>t>>v;
  91.                 E1[s].pb(t,v);
  92.                 E2[t].pb(s,v);
  93.         }
  94.  
  95.         dijkstra(d1,E1);
  96.         dijkstra(d2,E2);
  97.  
  98.         for(int i=1;i<=p;i++){
  99.                 d[i] = d1[i] + d2[i];
  100.         }
  101.  
  102.         sort(d.begin()+1,d.begin()+p+1);
  103.  
  104.         for(int i=1;i<=p;i++) d[i] += d[i-1];
  105.  
  106. //    cin>>p>>s;
  107. //    d.resize(p+1);
  108. //    for(int i=1;i<=p;i++) cin>>d[i], d[i] += d[i-1];
  109.  
  110.         ll l = 0, r = 1e16, val, k;
  111.         while(l<r){
  112.         ll m = (l+r)/2;
  113.         tie(val,k) = aliens(m);
  114.         //dbg(m, val, k);
  115.         if(k>s) l = m+1;
  116.         else r = m;
  117.         }
  118.         assert(l<1e16);
  119.         tie(val,k) = aliens(l);
  120.         cout<<val - s*l<<'\n';
  121.  
  122. }