TRAFFICN - Traffic Network
Tác giả: khuc_tuan
Ngôn ngữ: Pascal
// {$APPTYPE CONSOLE}
{$mode delphi}
uses math, sysutils;
type
PData = ^Data;
Data = record
v, c : integer;
n : PData;
end;
ArrData = array[1..10000] of PData;
ArrInt = array[1..10000] of integer;
procedure Add( var d : PData; v, c : integer);
var
p : PData;
begin
new(p);
p.v := v;
p.c := c;
p.n := d;
d := p;
end;
var
m, n : integer;
s, t : integer;
ke, ken : ArrData;
ds, dt : ArrInt;
h, pos : ArrInt;
nh : integer;
procedure pushdown(i : integer; var d : ArrInt);
var
j, t : integer;
begin
while 2*i <= nh do
begin
j := 2 * i;
if (j<nh) and (d[h[j+1]] < d[h[j]]) then inc(j);
if d[h[j]] < d[h[i]] then
begin
t := h[i]; h[i] := h[j]; h[j] := t;
pos[h[i]] := i;
pos[h[j]] := j;
i := j;
end
else break;
end;
end;
procedure pushup(i : integer; var d : ArrInt);
var
j, t : integer;
begin
while i >= 2 do
begin
j := i div 2;
if d[h[j]] > d[h[i]] then
begin
t := h[i]; h[i] := h[j]; h[j] := t;
pos[h[i]] := i;
pos[h[j]] := j;
i := j;
end
else break;
end;
end;
procedure addheap(i : integer; var d : ArrInt);
begin
inc(nh);
h[nh] := i;
pos[i] := nh;
pushup(nh, d);
end;
function extractmin(var d : ArrInt) : integer;
begin
extractmin := h[1];
h[1] := h[nh];
dec(nh);
pos[h[1]] := 1;
pushdown(1, d);
end;
procedure dijkstra(var ke : ArrData; s : integer; var d : ArrInt);
var
k, u, v, i : integer;
p : PData;
begin
for i:=1 to n do
d[i] := 1000000000;
fillchar( pos, sizeof(pos), -1);
d[s] := 0;
nh := 0;
addheap(s, d);
while nh > 0 do
begin
u := extractmin(d);
p := ke[u];
while p<>nil do
begin
v := p.v;
if d[v] > d[u] + p.c then
begin
d[v] := d[u] + p.c;
if pos[v]=-1 then addheap( v, d)
else
begin
k := pos[v];
pushup(k, d);
end;
end;
p := p.n;
end;
end;
end;
var
k, j, u, v, c, st, kk : integer;
res : integer;
begin
read(st);
for kk:=1 to st do
begin
read(n, m, k, s, t);
for j:=1 to n do
begin
ke[j] := nil;
ken[j] := nil;
end;
for j:=1 to m do
begin
read(u,v,c);
Add(ke[u], v, c);
Add(ken[v], u, c);
end;
dijkstra(ke, s, ds);
dijkstra(ken, t, dt);
res := ds[t];
for j:=1 to k do
begin
read(u,v,c);
res := min( res, ds[u] + dt[v] + c);
res := min( res, ds[v] + dt[u] + c);
end;
if res = 1000000000 then writeln(-1)
else writeln(res);
end;
end.