题目：http://acm.hdu.edu.cn/showproblem.php?pid=4411
- floyd处理出最短路
- 每个点拆为i、i+n，i到i+n连一条容量为1，费用为负无穷的边，代表这个城市必须访问
- i+n到j（j>i)分别建边，容量为1，费用为i、j最短路
- i+n到汇点建立容量为1费用为g[0][i]的边，代表会警察局
- 0到i建立容量为1费用为g[0][i]的边
- 0到汇点建立容量为k，费用为0的边，代表有的警察可能一直待在警察局
- 源点到0建立容量为k费用为0的边
ps：这题会有重边，以后一定要注意，每道题都要判重！
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxv = ;
typedef pair<int,int> P;
struct edge{
int to,cap,cost,rev;
};
int V;
vector<edge> g[maxv];
int h[maxv];
int dist[maxv];
int prevv[maxv],preve[maxv];
void addedge(int from,int to,int cap,int cost){
g[from].push_back(edge{to,cap,cost,g[to].size()});
g[to].push_back((edge{from,,-cost,g[from].size()-}));
}
int solve(int s,int t,int f){
int res = ;
memset(h,,sizeof(h)) ;
while(f > ){
priority_queue<P,vector<P>,greater<P> > que;
memset(dist,inf,sizeof(dist));
dist[s] = ;
que.push(P(,s));
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(dist[v] < p.first)
continue;
for(int i = ;i<g[v].size();i++){
edge &e = g[v][i] ;
if(e.cap> && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
que.push(P(dist[e.to],e.to));
}
}
}
if(dist[t] == inf)
return -;
for(int i = ;i<V;i++)
h[i] += dist[i];
int d = f;
for(int v = t;v!=s;v=prevv[v])
d = min(d,g[prevv[v]][preve[v]].cap);
f -= d;
res += d*h[t];
for(int v = t;v!=s;v = prevv[v]){
edge &e = g[prevv[v]][preve[v]];
e.cap -= d;
g[v][e.rev].cap += d;
}
}
return res;
}
int mp[][];
int main(){
int n,m,k;
while(scanf("%d%d%d",&n,&m,&k)){
if(!n && !m && !k)
break;
V = *n+;
int s = *n+,t = *n+;
for(int i = ;i<*n+;i++)
g[i].clear();
memset(mp,inf,sizeof(mp));
for(int i = ;i<=n;i++)
mp[i][i] = ;
int u,v,w;
while(m--){
scanf("%d%d%d",&u,&v,&w);
mp[u][v] = mp[v][u] = min(mp[u][v],w);
}
for(int k = ;k<=n;k++)
for(int i = ;i<=n;i++)
for(int j = ;j<=n;j++)
mp[i][j] = min(mp[i][j],mp[i][k]+mp[k][j]);
for(int i = ;i<=n;i++){
addedge(,i,,mp[][i]);
addedge(i+n,t,,mp[][i]);
addedge(i,i+n,,-);
for(int j = i+;j<=n;j++){
if(mp[i][j] != inf)
addedge(i+n,j,k,mp[i][j]);
}
}
addedge(s,,k,);
addedge(,t,k,);
cout << solve(s,t,k)+n* << endl;
}
return ;
}