题意：m个码头，每天从1号码头到m号码头，有些码头在某些天是不能经过的，每次修改路线要花cost，求n天最小总成本，总成本=n天经过权值和+修改路线次数*cost
跑n^2遍spfa预处理出第i天到第j天从1号码头到m号码头的最短距离t[i,j]
对于第i天，我们有两种选择
（1）从第一天开始就不改变航线
（2）从第j天开始改变航线一直保持到第i天
即f[i]=min{t[1,i]*i,f[j]+cost+t[j+1,i]*(i-j)}
最终答案f[n]
var n,m,cost,e,l :longint; x,y,z :longint; i,j :longint; last,que,dis :array[0..30] of longint; vis,ff :array[0..30] of boolean; flag :array[0..30,0..110] of boolean; t :array[0..110,0..110] of longint; f :array[0..110] of int64; pre,other,len :array[0..20010] of longint; function min(a,b:int64):int64; begin if a<b then exit(a) else exit(b); end; procedure connect(x,y,z:longint); begin inc(l); pre[l]:=last[x]; last[x]:=l; other[l]:=y; len[l]:=z; end; function spfa(a,b:longint):longint; var h,tl,cur,q,p,i,j:longint; begin fillchar(vis,sizeof(vis),false); fillchar(dis,sizeof(dis),127); fillchar(ff,sizeof(ff),true); for i:=a to b do for j:=1 to m do if flag[j,i] then ff[j]:=false; h:=0; tl:=1; que[1]:=1; dis[1]:=0; while (h<>tl) do begin h:=h mod 105+1; cur:=que[h]; vis[cur]:=false; q:=last[cur]; while (q<>0) do begin p:=other[q]; if (dis[p]>dis[cur]+len[q]) and ff[p] then begin dis[p]:=dis[cur]+len[q]; if not vis[p] then begin tl:=tl mod 105+1; que[tl]:=p; vis[p]:=true; end; end; q:=pre[q]; end; end; exit(dis[m]); end; begin read(n,m,cost,e); for i:=1 to e do begin read(x,y,z); connect(x,y,z); connect(y,x,z); end; // read(e); for i:=1 to e do begin read(x,y,z); for j:=y to z do flag[x,j]:=true; end; // for i:=1 to n do for j:=1 to n do t[i,j]:=spfa(i,j); // f[1]:=t[1,1]; for i:=2 to n do begin f[i]:=int64(t[1,i])*int64(i); for j:=1 to i-1 do f[i]:=min(f[i],f[j]+int64(cost)+int64(t[j+1,i])*int64(i-j)); end; writeln(f[n]); end. ——by Eirlys
