TRAFFICN - Traffic Network
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=10111;
oo=1000000011;
type
list=^node;
node=record
u,c:longint;
next:list;
end;
var
f1,f2:text;
hsize,ntest,test,n,m,s,t,k:longint;
ec,eu,ev:array[1..350] of longint;
h,hpos:array[1..MAXN] of longint;
d:array[0..1,1..MAXN] of longint;
ke,ke2:array[1..MAXN] of list;
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
i,u,v,c:longint;
begin
read(f1,n,m,k,s,t);
fillchar(ke,sizeof(ke),0);
fillchar(ke2,sizeof(ke2),0);
for i:=1 to m do
begin
read(f1,u,v,c);
add(v,c,ke[u]);
add(u,c,ke2[v]);
end;
for i:=1 to k do
read(f1,eu[i],ev[i],ec[i]);
end;
procedure swap(var a,b:longint);
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure downHeap(cs,i:longint);
var
j:longint;
begin
j:=i<<1;
while (j<=hsize) do
begin
if (j<hsize) and (d[cs,h[j+1]]<d[cs,h[j]]) then inc(j);
if (d[cs,h[j]]<d[cs,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(cs,i:longint);
var
j:longint;
begin
j:=i>>1;
while (i>1) and (d[cs,h[i]]<d[cs,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(cs,u:longint);
begin
inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
upHeap(cs,hsize);
end;
procedure pop(cs:longint; var u:longint);
begin
u:=h[1]; hpos[u]:=0;
swap(h[1],h[hsize]); hpos[h[1]]:=1;
dec(hsize); downHeap(cs,1);
end;
procedure solve;
var
u,v,c,i,kq:longint;
p:list;
begin
for u:=1 to n do d[0,u]:=oo;
d[0,s]:=0;
fillchar(hpos,sizeof(hpos),0); hsize:=0;
push(0,s);
while hsize>0 do
begin
pop(0,u);
p:=ke[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c; p:=p^.next;
if d[0,v]>d[0,u]+c then
begin
d[0,v]:=d[0,u]+c;
if hpos[v]=0 then push(0,v)
else upHeap(0,hpos[v]);
end;
end;
end;
for u:=1 to n do d[1,u]:=oo;
d[1,t]:=0;
fillchar(hpos,sizeof(hpos),0); hsize:=0;
push(1,t);
while hsize>0 do
begin
pop(1,u);
p:=ke2[u];
while p<>nil do
begin
v:=p^.u; c:=p^.c; p:=p^.next;
if d[1,v]>d[1,u]+c then
begin
d[1,v]:=d[1,u]+c;
if hpos[v]=0 then push(1,v)
else upHeap(1,hpos[v]);
end;
end;
end;
kq:=min(d[0,t],d[1,s]);
for i:=1 to k do
begin
u:=eu[i]; v:=ev[i]; c:=ec[i];
kq:=min(kq,d[0,u]+d[1,v]+c);
kq:=min(kq,d[0,v]+d[1,u]+c);
end;
if kq=oo then writeln(f2,-1)
else writeln(f2,kq);
end;
begin
openF;
read(f1,ntest);
for test:=1 to ntest do
begin
inp;
solve;
end;
closeF;
end.