题意：（n+1）个点（编号为0~n），m条带权双向边，初始在0号点K个人，要求：（1）所有城市全部被经过（一个人经过即算被经过）；（2）经过城市i前必须走完编号为编号为（0~i-1）的城市，且不能经过大于等于i的城市。在满足所有要求的前提下使得K个人走的总距离最小。
要求总距离最小，肯定是走满足条件下的两点最短距离，floyd预处理（注意floyd处理的时候k必须不超过i和j）
预处理完成后，再来考虑他们是怎么走的：
（1）在走完i号城市后，就不走了
（2）在走完i号城市后继续走（编号不一定连续，因为可能有其他人替他走了i+1号点）
增加源S和汇T，考虑满足题意的建图：
因为要求每个点都经过一次，所以把每个点拆成两个点i和i'
S -> 0 ' 容量为K 费用为0 【限流表示初始K个人】
i ->T 容量为1 费用为0 【第一次遍历完i城市】
S -> i' 容量为1 费用为0
i' -> j 容量为正无穷（可以走多次） 费用为dis[i,j]
能够发现，每一个点的第一次訪问都被转化成了一条从S出发的没有交叉的到汇的流，这样能够随意调整訪问顺序，保证了i訪问之前0~i-1都已经訪问过
var n,m,k,l,ss,st :longint; x,y,z,ans :longint; i,j :longint; vis :array[0..410] of boolean; map :array[0..155,0..155] of longint; que,dis,last :array[0..410] of longint; pre,other,len,c :array[0..41010] of longint; father :array[0..410] of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure connect(x,y,z,cost:longint); begin inc(l); pre[l]:=last[x]; last[x]:=l; other[l]:=y; len[l]:=z; c[l]:=cost; end; function spfa:boolean; var h,tl,cur,p,q,i:longint; begin for i:=1 to st do dis[i]:=maxlongint div 10; h:=0; tl:=1; que[1]:=ss; dis[ss]:=0; while (h<>tl) do begin h:=h mod 405 +1; cur:=que[h]; vis[cur]:=false; q:=last[cur]; while (q<>0) do begin p:=other[q]; if (dis[p]>dis[cur]+c[q]) and (len[q]>0) then begin dis[p]:=dis[cur]+c[q]; father[p]:=q; if not vis[p] then begin vis[p]:=true; tl:=tl mod 405+1; que[tl]:=p; end; end; q:=pre[q]; end; end; if dis[st]=maxlongint div 10 then exit(false) else exit(true); end; procedure update; var low,cur:longint; begin low:=maxlongint div 10; cur:=st; while (cur<>ss) do begin low:=min(low,len[father[cur]]); cur:=other[father[cur] xor 1]; end; cur:=st; while (cur<>ss) do begin dec(len[father[cur]],low); inc(len[father[cur] xor 1],low); inc(ans,low*c[father[cur]]); cur:=other[father[cur] xor 1]; end; end; procedure floyd; var i,j,k:longint; begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if ((k<=i) or (k<=j)) and (map[i,j]>map[i,k]+map[k,j]) then map[i,j]:=map[i,k]+map[k,j]; end; procedure build; var i,j:longint; begin connect(ss,1+n,k,0); connect(n+1,ss,0,0); for i:=2 to n do begin connect(ss,i+n,1,0); connect(i+n,ss,0,0); connect(i,st,1,0); connect(st,i,0,0); end; for i:=1 to n do for j:=i+1 to n do if map[i,j]<>maxlongint div 10 then begin connect(n+i,j,maxlongint div 10,map[i,j]); connect(j,n+i,0,-map[i,j]); end; end; begin read(n,m,k); inc(n); ss:=2*n+1; st:=ss+1; l:=1; for i:=1 to n do for j:=1 to n do if (i<>j) then map[i,j]:=maxlongint div 10; for i:=1 to m do begin read(x,y,z); inc(x); inc(y); if z<map[x,y] then map[x,y]:=z; map[y,x]:=map[x,y]; end; floyd; build; ans:=0; while spfa do update; writeln(ans); end. ——by Eirlys
