核心问题：给出长度为(b)的数组(c_i)，把每个数分到恰好(s)个集合中，最小化(sum c_i|c_i所在集合|)。
(b,sle 5000)
考虑最终状态下的两个集合(S,T)，假定(|S|le|T|)，如果有(xin S,yin T)，如果(x< y)，则把(x,y)交换一定不会更劣。
于是小的数放到大集合，大的数放到小的集合；除此外可以推广到：给(c_i)排序，那么一个集合一定对应着一段区间。
DP设(f_{i,j})表示搞了前(i)个数，选了(j)个集合，可以(O(n^3))做。
发现(f_{i,j})关于(j)是凸函数，于是可以凸优化。时间(O(n^2lg))。
似乎也可以决策单调性做。（类似这题？看着转移方程挺像的）
虽然会口胡但是之前从来就没有写过凸优化，这次是第一次写，一开始二分的斜率还取的是实数……凸优化二分的斜率不需要取实数的……
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cassert>
#include <cmath>
#define N 5005
#define M 50005
#define ll long long
#define fi first
#define se second
#define INF 1000000000000000000
int n,m,B,S;
struct EDGE{
int to,w;
EDGE *las;
};
struct Graph{
EDGE e[M];
int ne;
EDGE *last[N];
void link(int u,int v,int w){
e[ne]={v,w,last[u]};
last[u]=e+ne++;
}
} G0,G1;
ll c0[N],c1[N],c[N];
void S_P(Graph &G,ll dis[]){
static bool inq[N];
static queue<int> q;
memset(dis,127,sizeof(ll)*(n+1));
dis[B+1]=0;
q.push(B+1),inq[B+1]=1;
while (!q.empty()){
int x=q.front();
q.pop();
for (EDGE *ei=G.last[x];ei;ei=ei->las)
if (dis[x]+ei->w<dis[ei->to]){
dis[ei->to]=dis[x]+ei->w;
if (!inq[ei->to])
q.push(ei->to),inq[ei->to]=1;
}
inq[x]=0;
}
}
ll ps[N];
pair<ll,int> f[N];
inline void dp(ll w){
f[0]={0,0};
for (register int i=1;i<=B;++i){
f[i]={INF,0};
for (register int k=0;k<i;++k){
ll tmp=f[k].fi+(i-k)*(ps[i]-ps[k]);
if (tmp<f[i].fi)
f[i].fi=tmp,f[i].se=f[k].se+1;
}
f[i].fi-=w;
}
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d%d%d",&n,&B,&S,&m);
for (int i=1;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
G0.link(u,v,w);
G1.link(v,u,w);
}
S_P(G0,c0);
S_P(G1,c1);
for (int i=1;i<=B;++i)
c[i]=c0[i]+c1[i];
// for (int i=1;i<=B;++i)
// scanf("%lld",&c[i]);
sort(c+1,c+B+1);
for (int i=1;i<=B;++i)
ps[i]=ps[i-1]+c[i];
ll l=-ps[B]*B,r=0,res=0;
while (l<=r){
ll mid=l+r>>1;
dp(mid);
if (f[B].se<=S)
l=(res=mid)+1;
else
r=mid-1;
}
dp(res);
ll ans=f[B].fi+res*S;
printf("%lld
",ans-ps[B]);
return 0;
}