Cod sursa(job #67753)

Utilizator VmanDuta Vlad Vman Data 25 iunie 2007 13:54:32
Problema Branza Scor 0
Compilator fpc Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 1.78 kb
program sate;
const Nmax=30000;
      Mmax=100025;
      negativ=-21000000;
type pnod=^nod;
     nod=record
         ind:longint;
         next:pnod;
         end;
var n,x,y:integer;
    m,i:longint;
    a,b:array[1..Nmax]of pnod;
    st,dr:array[1..Mmax]of integer;
    d:array[1..Mmax]of longint;
    w:array[1..Mmax]of boolean;
    f:text;
    p:pnod;

function query(x,y:integer):longint;
var p:pnod;
    q:longint;
begin
if (x=y) then begin
                query:=0;
                exit;
              end;
{dupa capatul din stanga}
p:=a[x]^.next;
while p<>nil do begin
        if (dr[p^.ind]<y) then q:=d[p^.ind]+query(dr[p^.ind],y)
                else q:=d[p^.ind]-query(y,dr[p^.ind]);
        if (q>0) then begin
                        query:=q;
                        exit;
                 end;
        p:=p^.next;
end;
{dupa capatul din dreapta}
p:=b[y]^.next;
while p<>nil do begin
        if (st[p^.ind]<x) then q:=d[p^.ind]-query(st[p^.ind],x)
                else q:=d[p^.ind]+query(x,st[p^.ind]);
        if (q>0) then begin
                        query:=q;
                        exit;
                      end;
        p:=p^.next;
end;
query:=negativ;
end;

begin
assign(f,'sate.in');reset(f);
readln(f,n,m,x,y);
for i:=1 to n do begin
        new(a[i]);
        a[i]^.next:=nil;
        new(b[i]);
        b[i]^.next:=nil;
end;
for i:=1 to m do begin
        readln(f,st[i],dr[i],d[i]);
        {lista cu inceput}
        new(p);
        p^.ind:=i;
        p^.next:=a[st[i]]^.next;
        a[st[i]]^.next:=p;
        {lista cu sfarsit}
        new(p);
        p^.ind:=i;
        p^.next:=b[dr[i]]^.next;
        b[dr[i]]^.next:=p;
end;
close(f);
assign(f,'sate.out');rewrite(f);
write(f,query(x,y));
close(f);
end.