C++ 解法, 执行用时: 47ms, 内存消耗: 1944K, 提交时间: 2021-11-13 13:20:32

#include<bits/stdc++.h>
using namespace std;
const int N=500;
const int M=1e6;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
int n,m,s,t,K,dist[N][N];
int head[N],ver[M],edgec[M],edgef[M],nxt[M],tot=1;
int flow[N],pre[N],d[N],vis[N];
void addedge(int x,int y,int f,int c){
	ver[++tot]=y,edgec[tot]=c,edgef[tot]=f;
	nxt[tot]=head[x];head[x]=tot;
	ver[++tot]=x,edgec[tot]=-c,edgef[tot]=0;
	nxt[tot]=head[y];head[y]=tot;
}
queue<int>que;
int spfa(){
	memset(pre,-1,sizeof(pre));
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	flow[s]=INF,vis[s]=1,d[s]=0;
	que.push(s);
	while(!que.empty()){
		int x=que.front();que.pop();
		vis[x]=0;
		for(int i=head[x];i!=-1;i=nxt[i]){
			int y=ver[i];
			if(d[y]>d[x]+edgec[i] && edgef[i]>0){
				d[y]=d[x]+edgec[i];
				pre[y]=i;
				flow[y]=min(flow[x],edgef[i]);
				if(!vis[y]){
					vis[y]=1;
					que.push(y);
				}
			}
		}
	}
	return d[t]!=INF;
}
int EK(){
	int ans=0;
	while(spfa()){
		int cur=t;
		while(cur!=s){
			int i=pre[cur];
			edgef[i]-=flow[t];
			edgef[i^1]+=flow[t];
			cur=ver[i^1];
		}
		ans+=flow[t]*d[t];
	}
	return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>K;
    memset(dist,0x3f,sizeof(dist));
    memset(head,-1,sizeof(head));
    for(int i=0;i<=n;i++)dist[i][i]=0;
    for(int i=1;i<=m;i++){
    	int a,b,l;cin>>a>>b>>l;
    	dist[a][b]=dist[b][a]=min(dist[a][b],l);
	}
	s=2*n+1,t=s+1;
	for(int k=0;k<=n;k++)
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				if(k<=max(i,j))dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	addedge(s,0,K,0);
	for(int i=1;i<=n;i++){
		addedge(s,i,1,0);
		addedge(i+n,t,1,0);
	}
	for(int i=0;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			addedge(i,j+n,1,dist[i][j]);
	cout<<EK();
    return 0;
}