NK05DSRT - Sa mạc
Tác giả: RR
Ngôn ngữ: Pascal
//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung (algorithm by taek)
{$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=101;
oo=1000000000000;
type
list=^node;
node=record
u,c:longint;
next:list;
end;
var
f1,f2:text;
test,n,gh,hsize:longint;
ke:array[1..MAXN] of list;
h,hpos:array[1..MAXN] of longint;
need:array[1..MAXN] of int64;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure add(u,c:longint; var a:list);
var p:list;
begin
new(p); p^.u:=u; p^.c:=c;
p^.next:=a; a:=p;
end;
procedure inp;
var
m,u,v,c:longint;
begin
read(f1,n,m,gh);
fillchar(ke,sizeof(ke),0);
for m:=1 to m do
begin
read(f1,u,v,c);
add(u,c,ke[v]);
add(v,c,ke[u]);
end;
end;
procedure ans;
begin
if need[1]=oo then writeln(f2,-1)
else writeln(f2,need[1]);
end;
//Xu ly heap
procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint);
var
j:longint;
begin
j:=i<<1;
while (j<=hsize) do
begin
if (j<hsize) and (need[h[j+1]]<need[h[j]]) then inc(j);
if (need[h[j]]<need[h[i]]) then
begin
swap(hpos[h[i]],hpos[h[j]]);
swap(h[i],h[j]);
end;
i:=j; j:=i<<1;
end;
end;
procedure upHeap(i:longint);
var
j:longint;
begin
j:=i>>1;
while (i>1) and (need[h[i]]<need[h[j]]) do
begin
swap(hpos[h[i]],hpos[h[j]]);
swap(h[i],h[j]);
i:=j; j:=i>>1;
end;
end;
procedure push(u:longint);
begin
inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
upHeap(hsize);
end;
procedure pop(var u:longint);
begin
u:=h[1]; hpos[u]:=0;
swap(h[1],h[hsize]); hpos[h[1]]:=1;
dec(hsize); downHeap(1);
end;
procedure solve;
var
u,v:longint;
x,one,c:int64;
p:list;
begin
for u:=1 to n-1 do need[u]:=oo; need[n]:=0;
hsize:=0; fillchar(hpos,sizeof(hpos),0); push(n);
while hsize>0 do
begin
pop(u);
p:=ke[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c; p:=p^.next;
//Khong the qua canh (u,v)
if c>gh then continue;
//Chi can luong <=gh-c de den dich (chi can qua canh (u,v) 1 lan)
if need[u]<=gh-c then x:=need[u]+c
else if gh-c<<1<=0 then continue
else
begin
//Luong nuoc chuyen duoc trong 1 lan
one:=(need[u]-(gh-c)-1) div (gh-c<<1)+1;
//Luong nuoc can
x:=need[u]+(one<<1+1)*c;
end;
if x<need[v] then
begin
need[v]:=x;
if hpos[v]=0 then push(v)
else upHeap(hpos[v]);
end;
end;
end;
end;
begin
openF;
read(f1,test);
for test:=1 to test do
begin
inp;
solve;
ans;
end;
closeF;
end.