ac1149.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1149;
const
  tests=8;//A chr(26) at eof, causing RE 106. So gotta do like this!
  maxn=300;
var
  t1,t2,state:array[1..maxn]of byte;
  len:array[1..maxn,1..maxn]of byte;
  time:array[0..maxn]of cardinal;
  pre:array[1..maxn]of word;
  v:array[1..maxn]of boolean;
  u,n,m,src,tar,i,a,b,c,d:word;
function gcd(a,b:byte):byte;
  var
    t:byte;
  begin
    if a<b then begin t:=a;a:=b;b:=t;end;
    repeat
      t:=a mod b;a:=b;b:=t;
    until t=0;
    gcd:=a;
  end;
procedure go(x,y:word);
  var
    lcm,sx,sy,t,ex,ey:word;
  procedure elapse(a:longint);
    begin
      sx:=(sx+a) mod t2[x];
      sy:=(sy+a) mod t2[y];
      inc(t,a);
    end;
  begin
    lcm:=t2[x]*t2[y] div gcd(t2[x],t2[y]);
    sx:=state[x];sy:=state[y];
    t:=0;elapse(time[x]);t:=0;
    while ((sx<t1[x])<>(sy<t1[y])) and (t<lcm) do begin
      if sx<t1[x] then ex:=t1[x]-sx else ex:=t2[x]-sx;
      if sy<t1[y] then ey:=t1[y]-sy else ey:=t2[y]-sy;
      if ex<ey then elapse(ex) else elapse(ey);
    end;
    if t<lcm then begin
      inc(t,time[x]+len[x,y]);
      if t<time[y] then begin
        time[y]:=t;pre[y]:=x;
      end;
    end;
  end;
procedure back(x:word);
  begin
    if time[x]=0 then
      write(x)
    else begin
      back(pre[x]);
      write(' ',x);
    end;
  end;
begin
  for u:=1 to tests do begin
    read(n,m,src,tar);
    for i:=1 to n do begin
      read(a,b,c,d);
      t1[i]:=c;t2[i]:=c+d;
      if a=0 then state[i]:=c-b else state[i]:=c+d-b;
    end;
    fillchar(len,sizeof(len),255);
    for i:=1 to m do begin
      read(a,b,c);
      if c<len[a,b] then begin
        len[a,b]:=c;len[b,a]:=c;
      end;
    end;

    fillchar(time,sizeof(time),255);time[src]:=0;
    fillchar(v,sizeof(v),0);
    repeat
      v[src]:=true;
      for i:=1 to n do
        if not v[i] and (len[src,i]<255) then
          go(src,i);
      src:=0;
      for i:=1 to n do
        if not v[i] and (time[i]<time[src]) then src:=i;
    until (src=0) or (src=tar);
    if src=0 then
      writeln('Poor OIBen.')
    else begin
      writeln(time[tar]);
      back(tar);
      writeln;
    end;
  end;
end.