倍增好题,f[p,i,j]表示i到j经过了2^p条边走过的最短路径

显然f[p+1]可以由f[p]转移来

然后对n二进制拆分累加即可

1 const inf=9999999999; 2  3 var map,pm:array[0..110,0..110] of int64; 4     f,pf:array[0..110] of int64; 5     v:array[0..1010] of longint; 6     j,z,x,y,s,t,n,m,e,i:longint; 7  8 function min(a,b:int64):int64; 9   begin10     if a>b then exit(b) else exit(a);11   end;12 13 function get(x:longint):longint;14   begin15     if v[x]=0 then16     begin17       inc(t);18       v[x]:=t;19     end;20     exit(v[x]);21   end;22 23 procedure time1;24   var i,j:longint;25   begin26     pf:=f;27     for i:=1 to t do28     begin29       f[i]:=inf;30       for j:=1 to t do31         f[i]:=min(f[i],pf[j]+map[j,i]);32     end;33   end;34 35 procedure time2;36   var i,j,k:longint;37   begin38     pm:=map;39     for i:=1 to t do40       for j:=1 to t do41       begin42         map[i,j]:=inf;43         for k:=1 to t do44           map[i,j]:=min(map[i,j],pm[i,k]+pm[k,j]);45       end;46   end;47 48 procedure work(x:longint);49   begin50     while x>0 do51     begin52       if x mod 2=1 then time1;53       x:=x shr 1;54       if x<>0 then time2;55     end;56   end;57 58 begin59   readln(n,m,s,e);60   for i:=1 to 100 do61     for j:=1 to 100 do62       map[i,j]:=inf;63   for i:=1 to m do64   begin65     readln(z,x,y);66     x:=get(x);67     y:=get(y);68     map[x,y]:=z;69     map[y,x]:=z;70   end;71   s:=get(s);72   e:=get(e);73   for i:=1 to t do74     f[i]:=inf;75   f[s]:=0;76   work(n);77   writeln(f[e]);78 end.