这道题么= =还是有些恶心的，第一次写带上下界的网络流，整个人都萌萌哒~~~
首先先预处理得最短路后
直接用费用流做就行了。
第一次写，还是挺好写的= =
CODE：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 310
#define maxm 100000
struct edges{
int to,next,cap,dist;
}edge[maxm];
int next[maxn],l;
void addedge(int x,int y,int z,int d){
l++;
edge[l*2]=(edges){y,next[x],z,d};next[x]=l*2;
edge[l*2+1]=(edges){x,next[y],0,-d};next[y]=l*2+1;
}
int inf;
int dist[maxn],w[maxn],s,t,cnt;
bool b[maxn];
queue<int> q;
bool spfa() {
for (int i=1;i<=cnt;i++) dist[i]=inf;
dist[s]=0;
q.push(s);
while (!q.empty()) {
int u=q.front();q.pop();
b[u]=0;
for (int i=next[u];i;i=edge[i].next)
if (edge[i].cap&&edge[i].dist+dist[u]<dist[edge[i].to]) {
dist[edge[i].to]=dist[u]+edge[i].dist;
w[edge[i].to]=i;
if (!b[edge[i].to]) {
b[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
return dist[t]!=inf;
}
int ans;
int mcmf(int ss,int tt){
s=ss,t=tt;
while (spfa()) {
int x=t,flow=inf;
while (x!=s) {
flow=min(flow,edge[w[x]].cap);
x=edge[w[x]^1].to;
}
ans+=flow*dist[t];
x=t;
while (x!=s) {
edge[w[x]].cap-=flow;
edge[w[x]^1].cap+=flow;
x=edge[w[x]^1].to;
}
}
}
int dis[maxn][maxn],f[maxn][maxn],id[maxn][2];
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
memset(f,10,sizeof(f));
inf=f[0][0];
for (int i=1;i<=m;i++) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
f[x][y]=f[y][x]=min(f[x][y],z);
}
for (int i=0;i<=n;i++) f[i][i]=0;
for (int k=0;k<=n;k++) {
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
for (int i=0;i<=n;i++) dis[i][k]=f[i][k];
}
for (int i=0;i<=n;i++) id[i][0]=++cnt;
for (int i=0;i<=n;i++) id[i][1]=++cnt;
int s=++cnt,t=++cnt;
addedge(id[0][0],id[0][1],k,0);
for (int i=1;i<=n;i++) {
addedge(id[0][1],id[i][0],inf,dis[0][i]);
addedge(id[i][1],id[n][1],inf,0);
addedge(id[i][0],id[i][1],inf,0);
addedge(s,id[i][1],1,0);
addedge(id[i][0],t,1,0);
}
for (int i=0;i<n;i++)
for (int j=i+1;j<=n;j++)
if (dis[i][j]!=inf) addedge(id[i][1],id[j][0],inf,dis[i][j]);
addedge(id[n][1],id[0][0],inf,0);
mcmf(s,t);
next[s]=next[t]=0;
next[id[n][1]]=edge[next[id[n][1]]].next;
next[id[0][0]]=edge[next[id[0][0]]].next;
mcmf(id[0][0],id[n][1]);
printf("%d\n",ans);
return 0;
}