出题人真 口袋迷
很容易发现这是一道费用流的题目
很显然这个问题有两个难点：
保证走到某个点时之前序号的点都被走过
保证每个点都走
对于1，我们换个说法，一个人走到该点时经过的点的序号都小于该点----->3
只要满足了2和3，就一定满足1
现在来看3，也就是说两个点之间的最短路i，j，必须由k（k<j) 来更新
很像是floyd，事实上我们只要改一改floyd就能满足3
下面的问题就是，怎么满足2，也就是称之为有下界的网络流
这里学习了一个非常厉害的方法解决此类问题：
加无穷小边连接汇点
对于这道题，我们把除了0号点的以外点拆成两个点，之间连两条边
一条流量为1，费用为负无穷；一条流量为无穷，费用为0
什么意思呢？第二条边好理解，表示每个点都可以被经过无数次
第一条边什么意思呢？保证每个点都被走过；
因为这条边的费用为极小边，根据费用流的算法，这条边一定会被走过，等价于这个点一定会被走过；
最后计算总费用的时候我们再把负费用弄掉即可
后记：
话说，我在省选的前几天做了这道题目，说了都是泪啊；
考试的时候D2 T1同样也是有下界的网络流，比这题还简单，
这不过是边的容量下界是1,（一样的道理，在每条边的基础上加一条流为1，费用为这条边的费用-极小量即可）
我也很好的写出了处理有下界的网络流的方法；
可我偏偏脑抽的用到了邻接矩阵，这样就毫无意外的被重边卡死了T T
自作孽，不可活…………
UPD：注意这个程序虽然能过但有点问题，具体见后续
const inf=;
bi=;
type node=record
from,point,cost,flow,next:longint;
end; var edge:array[..] of node;
q:array[..] of longint;
a:array[..,..] of longint;
p,pre,d:array[..] of longint;
v:array[..] of boolean;
len,x,y,z,ans,n,m,k,i,j,w,t:longint; procedure add(x,y,f,w:longint);
begin
inc(len);
edge[len].from:=x;
edge[len].point:=y;
edge[len].flow:=f;
edge[len].cost:=w;
edge[len].next:=p[x];
p[x]:=len;
end; function spfa:boolean; //网络流基本模板
var i,f,r,x,y:longint;
begin
fillchar(v,sizeof(v),false);
for i:= to t do
d[i]:=inf;
d[]:=;
f:=;
r:=;
q[]:=;
v[]:=true;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
begin
if d[y]>d[x]+edge[i].cost then
begin
d[y]:=d[x]+edge[i].cost;
pre[y]:=i;
if not v[y] then
begin
v[y]:=true;
inc(r);
q[r]:=y;
end;
end;
end;
i:=edge[i].next;
end;
inc(f);
end;
if d[t]=inf then exit(false) else exit(true);
end; procedure mincost; //费用流
var i,j:longint;
begin
while spfa do
begin
i:=t;
while i<> do
begin
j:=pre[i];
dec(edge[j].flow); //每次只会流一个人
inc(edge[j xor ].flow);
i:=edge[j].from;
end;
ans:=ans+d[t];
end;
end; begin
readln(n,m,w);
inc(n);
len:=-;
fillchar(p,sizeof(p),);
for i:= to n do
begin
for j:= to n do
a[i,j]:=inf;
a[i,i]:=;
end;
t:=*n+;
for i:= to m do
begin
readln(x,y,z);
inc(x); //仅仅是为了方便
inc(y);
if a[x,y]>z then
begin
a[x,y]:=z;
a[y,x]:=z;
end;
end;
add(,,w,); //一共有w个人，自然流量为w
add(,,,);
for i:= to n do
begin
add(i,i+n,,-bi); //处理下界网络流简单快捷的方法
add(i+n,i,,bi);
add(i+n,t,,); //每个人都可以停在当前点不走，流直接流出
add(t,n+i,,);
end;
for k:= to n do
begin
for i:= to n do
if i<>k then
for j:= to n do
if (i<>j) and (j<>k) then
a[i,j]:=min(a[i,j],a[i,k]+a[k,j]);
if k<> then
begin
add(,k,,a[,k]);
add(k,,,-a[,k]);
end;
for i:= to k- do // 边做边建图，显然这时候，i到k的最短路径一定是由编号小于k的点更新来的
begin
add(i+n,k,,a[i,k]); //这个地方和上面流量为什么是1呢？点i到下一个点j可行最小路径只要走一次，
如果这条路径实际需要走多次的话，那必然有点i到点k的可行最短路径由ij可行最短路更新的来
于是下一次找增广路的时候，我们直接走ik之间最短路即可
所以这里我们把每条路径流量限制为1，这样寻找增广路的速度会更快
（当然像考试时拿不准还是写成inf吧
add(k,i+n,,-a[i,k]);
end;
end;
mincost;
writeln(ans+(n-)*bi); //修正ans
end.