(*

I semafori (IOI 1999)
Copyright (C) 2000 Paolo Boldi

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*)

program Ioi9921;
(* Il programma viene realizzato come una normale ricerca del cammino minimo,
   aggiornando i costi in modo dinamico *)

const maxj=300;         (* Numero max. incroci *)
      inf=high(integer);          (* Infinito *)
      nomefin='lights10.inp';
      nomefout='myl10.out';
type colore=(blu,rosso);
     incrocio=1..maxj;
var
   nj: incrocio;         (* Numero incroci *)
   colin: array [incrocio] of colore; (* Colore iniziale *)
   trans: array [incrocio] of integer;   (* Tempo residuo per il col. iniziale *)
   per: array [incrocio,colore] of integer; (* Durata di ciascun colore *)
   sorg,dest: incrocio;        (* Sorgente/destinazione *)
   d: array [incrocio] of integer;
   p: array [incrocio] of 1..maxj;

(* Per le lunghezze delle strade, anziche' usare una matrice di adiacenza
   pesata (sarebbe 300x300...), usiamo una struttura a cui pero' accediamo
   come con una matrice di adiacenza *)
type pstrada=^strada;
     strada=record
                 arrivo: incrocio;
                 lun: integer;
                 next: pstrada
           end;
var strade: array [incrocio] of pstrada;
    (* Se i->j ha lunghezza l e i e' il minimo, strade[i] contiene
       l'elemento (j,l,...) *)

procedure inserisci_strada(i,j: incrocio; l: integer);
var t: incrocio;
    n: pstrada;
begin
     if (i>j) then begin t:=i; i:=j; j:=t end;
     new(n); n^.arrivo:=j; n^.lun:=l; n^.next:=strade[i];
     strade[i]:=n
end;

function lung(i,j: incrocio): integer;
var t: incrocio;
    n: pstrada;
begin
     if (i>j) then begin t:=i; i:=j; j:=t end;
     n:=strade[i];
     while (n<>nil) and (n^.arrivo<>j) do n:=n^.next;
     if (n=nil) then lung:=inf else lung:=n^.lun
end;

(************ FUNZIONI DI SERVIZIO **)

function min(a,b: integer): integer;
begin
     if (a<b) then min:=a else min:=b
end;

function somma(a,b: integer): integer;
begin
     if (a=inf) or (b=inf) then somma:=inf
     else somma:=a+b
end;

function altro(c: colore): colore;
(* Fornisce l'altro colore *)
begin
     if (c=rosso) then altro:=blu else altro:=rosso
end;

(****)

function col(j: incrocio; t: integer; var tr: integer): colore;
(* Fornisce il colore del semaforo j all'inizio del time-slot t,
   e da' in tr il tempo residuo per quel colore *)
var temp: integer;
begin
     temp:=(t-trans[j]) mod (per[j,blu]+per[j,rosso]);
     while (temp<0) do temp:=temp+per[j,blu]+per[j,rosso];
     (* se X e' il colore iniz. e Y l'altro, temp contiene la posiz. nel
        blocco YYYYYXXX *)
     if (temp<per[j,altro(colin[j])]) then
        begin
             tr:=per[j,altro(colin[j])]-temp;
             col:=altro(colin[j])
        end
     else
         begin
              tr:=per[j,blu]+per[j,rosso]-temp;
              col:=colin[j]
         end
end;

function lungt(j,i: incrocio; t: integer): integer;
(* Se si arriva all'incrocio j all'istante t, e si vuole percorrere la strada j->i,
   quanto tempo dopo si giungera' all'altra estremita'? *)
var trj,tri: integer;
    cj,ci: colore;
begin
     cj:=col(j,t,trj);
     ci:=col(i,t,tri);
     if (ci=cj) then
        lungt:=lung(j,i)
     else if (trj<>tri) then
        lungt:=somma(lung(j,i),min(trj,tri))
     else if (per[j,altro(cj)]<>per[i,altro(ci)]) then
        lungt:=somma(lung(j,i),trj+min(per[j,altro(cj)],per[i,altro(ci)]))
     else if (per[j,cj]<>per[i,ci]) then
        lungt:=somma(lung(j,i),trj+per[j,altro(cj)]+min(per[i,ci],per[j,cj]))
     else lungt:=inf
end;

procedure minp;
(* Cerca il cammino minimo, riempiendo le matrici d (matrice delle distanze minime)
   e p (matrice per la ricostruzione del cammino minimo) *)
var visited: array [incrocio] of boolean;
    i,mini: incrocio;
    c,minv: integer;
begin
     for i:=1 to nj do
         begin
              visited[i]:=(i=sorg);
              p[i]:=sorg;
              d[i]:=lungt(sorg,i,0)
         end;
     while (not visited[dest]) do
           begin
                minv:=inf;
                for i:=1 to nj do
                    if (not visited[i]) and (d[i]<minv) then
                       begin
                            minv:=d[i];
                            mini:=i
                       end;
                if (minv=inf) then break;
                visited[mini]:=true;
                for i:=1 to nj do
                    begin
                         c:=somma(d[mini],lungt(mini,i,d[mini]));
                         if (d[i]>c) then
                            begin
                                 d[i]:=c;
                                 p[i]:=mini
                            end
                    end
           end
end;

procedure outp(var f: text; j: incrocio);
(* Stampa il cammino minimo fino all'incrocio j sul file f *)
begin
     if (j<>sorg) then
        outp(f,p[j]);
     write(f,j,' ')
end;

procedure out;
(* Stampa dell'output *)
var f: text;
begin
     assign(f,nomefout);
     rewrite(f);
     if (d[dest]=inf) then
            writeln(f,0)
     else
         begin
              writeln(f,d[dest]);
              outp(f,dest);
              writeln(f)
         end;
     close(f)
end;

procedure inp;
(* Lettura dell'input *)
var f: text;
    nl,j: integer;
    a,b: incrocio;
    l: integer;
    c: char;
begin
     assign(f,nomefin);
     reset(f);
     readln(f,sorg,dest);
     readln(f,nj,nl);
     for j:=1 to nj do
         begin
              readln(f,c,trans[j],per[j,blu],per[j,rosso]);
              if (c='B') then colin[j]:=blu else colin[j]:=rosso
         end;
     for a:=1 to nj do strade[a]:=nil;
     for j:=1 to nl do
         begin
              readln(f,a,b,l);
              inserisci_strada(a,b,l)
         end;
     close(f)
end;

(* MAIN *)
begin
     inp;
     minp;
     out
end.