ac1194.pas

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· PAS 代码 · 共 57 行

program tju1194;
const
  maxnum=100;
  maxn=30;
  maxk=300;
var
  id:array[1..maxnum]of byte;
  len:array[1..maxn,1..maxn]of byte;
  start,fin:array[1..maxk]of longint;
  time:array[0..maxn]of word;
  v:array[1..maxn]of boolean;
  n,k,i,x,y,f,r:longint;
function cost(x,y:byte):word;
  var
    i,t:word;
  begin
    fillchar(time,sizeof(time),255);time[x]:=0;
    fillchar(v,sizeof(v),0);v[y]:=true;
    cost:=0;
    repeat
      v[x]:=true;
      for i:=1 to n do
        if len[x,i]>0 then begin
          t:=time[x]+len[x,i];
          if t>cost then cost:=t;
          if t<time[i] then time[i]:=t;
        end;
      x:=0;
      for i:=1 to n do
        if not v[i] and (time[i]<time[x]) then x:=i;
    until x=0;
  end;
begin
  repeat
    fillchar(len,sizeof(len),0);
    read(n);
    for i:=1 to n do begin
      read(x);id[x]:=i;
    end;
    read(k);
    for i:=1 to k do begin
      read(x,y);x:=id[x];y:=id[y];read(len[x,y]);len[y,x]:=len[x,y];
    end;

    read(k);
    for i:=1 to k do begin
      read(x,start[i],x,y);
      fin[i]:=start[i]+cost(id[x],id[y]);
    end;

    read(x);y:=0;
    for i:=1 to k do
      if (x>=start[i]) and (x<fin[i]) then inc(y);
    writeln(y);
  until seekeof;
end.