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.

Download