【题意】
t条路,问从s到e经过n条边的最小路程
【输入】
第一行n、t、s、e
接下来t行为边的长度、边的两个端点编号
【输出】
从s到e经过n条边最小路程
做flyod,本身需要枚举n次,基于快速幂思想加速
需要注意的是评测网站和noi的pascal内核都为2.0.4
递归很容易溢出
program poj3613; type arr=array [0..201,0..201] of int64; var n,t,i,j,k,s,e,tot,all:longint; dl,map,u,v,c:array [0..10001] of longint; dis,root,temp,p:arr; function min (a,b:int64):int64; begin if a<b then exit(a) else exit(b); end; procedure swap (var a,b:longint); var i:longint; begin i:=a; a:=b; b:=i; end; procedure qsort (s,e:longint); var i,j,k:longint; begin if s>=e then exit; i:=s; j:=e; k:=dl[(s+e) div 2]; while i<=j do begin while dl[i]<k do inc(i); while dl[j]>k do dec(j); if i>j then break; swap(dl[i],dl[j]); inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; begin fillchar(root,sizeof(root),63); read(n,t,s,e); tot:=0; for i:=1 to t do begin read(c[i],u[i],v[i]); inc(tot); dl[tot]:=u[i]; inc(tot); dl[tot]:=v[i]; end; qsort(1,tot); all:=1; k:=1; for i:=1 to tot do begin if dl[i]<>dl[k] then begin k:=i; inc(all); end; map[dl[i]]:=all; end; for i:=1 to t do begin root[map[u[i]],map[v[i]]]:=min(root[map[u[i]],map[v[i]]],c[i]); root[map[v[i]],map[u[i]]]:=min(root[map[v[i]],map[u[i]]],c[i]); end; tot:=1; while n>0 do begin dl[tot]:=n; n:=n div 2; inc(tot); end; dec(tot); dis:=root; dec(tot); while tot>0 do begin p:=dis; fillchar(temp,sizeof(temp),63); for i:=1 to all do for j:=1 to all do for k:=1 to all do temp[i,k]:=min(temp[i,k],p[i,j]+p[j,k]); fillchar(dis,sizeof(dis),63); if dl[tot] and 1 = 1 then for i:=1 to all do for j:=1 to all do for k:=1 to all do dis[i,k]:=min(dis[i,k],temp[i,j]+root[j,k]) else dis:=temp; dec(tot); end; s:=map[s]; e:=map[e]; writeln(dis[s,e]); end.