倍增好题,f[p,i,j]表示i到j经过了2^p条边走过的最短路径
显然f[p+1]可以由f[p]转移来
然后对n二进制拆分累加即可
const inf=; var map,pm:array[..,..] of int64;
f,pf:array[..] of int64;
v:array[..] of longint;
j,z,x,y,s,t,n,m,e,i:longint; function min(a,b:int64):int64;
begin
if a>b then exit(b) else exit(a);
end; function get(x:longint):longint;
begin
if v[x]= then
begin
inc(t);
v[x]:=t;
end;
exit(v[x]);
end; procedure time1;
var i,j:longint;
begin
pf:=f;
for i:= to t do
begin
f[i]:=inf;
for j:= to t do
f[i]:=min(f[i],pf[j]+map[j,i]);
end;
end; procedure time2;
var i,j,k:longint;
begin
pm:=map;
for i:= to t do
for j:= to t do
begin
map[i,j]:=inf;
for k:= to t do
map[i,j]:=min(map[i,j],pm[i,k]+pm[k,j]);
end;
end; procedure work(x:longint);
begin
while x> do
begin
if x mod = then time1;
x:=x shr ;
if x<> then time2;
end;
end; begin
readln(n,m,s,e);
for i:= to do
for j:= to do
map[i,j]:=inf;
for i:= to m do
begin
readln(z,x,y);
x:=get(x);
y:=get(y);
map[x,y]:=z;
map[y,x]:=z;
end;
s:=get(s);
e:=get(e);
for i:= to t do
f[i]:=inf;
f[s]:=;
work(n);
writeln(f[e]);
end.