求卡常

#include<bits/stdc++.h>
#define fs(i,x,y,z) for(int i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(int i=x;i>=y;i+=z)
#define int long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
#define pii pair<int,int>
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x3f3f3f3f;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
struct edge{int v,nx,w;}e[N<<1];
int hd[N],totm,dis[5005][5005];
void add(int u,int v,int w){e[++totm].v=v;e[totm].nx=hd[u];hd[u]=totm;e[totm].w=w;} 
priority_queue<pii,vector<pii>,greater<pii>> q;
void dij(int s){
	dis[s][s]=0;while(!q.empty()) q.pop();
	q.push({0,s});
	while(!q.empty()){
		pii now=q.top();q.pop();
		int dist=now.first,u=now.second;
		if(dist!=dis[s][u]) continue;
		for(int i=hd[u];i;i=e[i].nx){
			int v=e[i].v;if(dis[s][v]>dis[s][u]+e[i].w){
				dis[s][v]=dis[s][u]+e[i].w;
				q.push({dis[s][v],v});
			}
		}
	}
}
int n,m,res,b,s,biz[N],d[N],f[5005][5005];//len[i]记录他要屯几个 
bool cmp(int x,int y){return x>y;}
signed main(){
//	ms(dis,0x3f);
	n=read(),b=read(),s=read(),m=read(); 
	fs(i,1,n,1) fs(j,1,n,1) dis[i][j]=1e14;
	fs(i,1,m,1){
		int u=read(),v=read(),w=read();
		add(u,v,w);//add(v,u);
	}
	fs(i,1,b+1,1) dij(i);
//	fs(i,1,b,1) fs(j,1,n,1) cout<<dis[i][j]<<" \n"[j==n];
	fs(i,1,b,1) biz[i]=dis[i][b+1]+dis[b+1][i];
	sort(biz+1,biz+b+1);
	fs(i,1,b,1) d[i]=d[i-1]+biz[i];//d是b的前缀和 
//	fs(i,1,b,1) cout<<biz[]
	fs(j,0,s,1) fs(i,0,b,1) f[i][j]=1e18;
	f[0][0]=0;
	fs(j,1,s,1) fs(i,1,b,1) fs(k,i-i/j,i-1,1) f[i][j]=min(f[i][j],f[k][j-1]+(i-k-1)*(d[i]-d[k])),assert(i-k-1>=0),assert(d[i]-d[k]>=0);
	cout<<f[b][s];
	return 0;
}
//T1没啥思路，先开T2 
//先用dij求出全员最短路再说 
//转车=边数-1 
//我们对于每个点，求出同时满足到1，到我都满足\le k且最大的
//那怎么处理相同
//因为他最多有可能和三个点相同
//所以记录前三个
//ez
//然后怎么做？ 
//枚举B和C，然后O1判断即可
//感觉A比B水啊 
//没去重 
//考虑：假如做一个项目的是点团S，并且|S|=k
//则对于每个点x，他需要跑到其他所有点去，代价是(k-1)d(x,b+1)与\sum d(b+1,i)[i\ne x]
//全部加起来，就是(k-1) \sum d(x,b+1)+(k-1)\sum d(b+1,i)
//综上所述，一个团的贡献是(k-1) \sum{x\in S} (d(x,b+1)+d(b+1,x))
//所以我们现在的任务就是分配
//显然这两个d都能计算出来 
//那么最优肯定是让最小的承担最多，A B C D EEEEEEEEE这样？
//错了，因为A B C D D的话可以让五号点的贡献从k-1变成1，显然更好，但他也会加上那个
//本质：分段，使得\sum (len-1)f[i]最小
//设f[i][j]表示前i个数分j段的最小代价
//f[j+1][i+d]=min(f[j+1][i+d],f[j][i]+(sd[i+d]-sd[i])*(d-1))[i+1,i+d]是第j+1段 
//f[j][i]=min(f[j][i],f[j-1][i-d]+(sd[i]-sd[i-d])*(d-1))
//T(i)=min(f[i-d]+sd[i]*d-sd[i]-sd[i-d]*d+sd[i-d])
//f[j][i]=min(f[j][i],f[j-1][d]+(i-d-1)*(sd[i]-sd[d]))，d+1到i是这一段
//拆开：f[j][i]=f[j-1][d]+i*sd[i]-i*sd[d]-d*sd[i]+d*sd[d]-sd[i]+sd[d]
//f[j][i]-i*sd[i]+sd[i]=f[j-1][d]-i*sd[d]-d*sd[i]+d*sd[d]+sd[d]
//i*sd[d]-d*sd[i]
//x y=f[j-1][d]+d*sd[d]+sd[d] k b=f[j][i]-i*sd[i]+sd[i]
//然后咋做？ 
//考虑一个性质：每段的长度一定大于等于上一段