ac1136.pas

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

program tju1136;
const
  maxn=100;
  maxm=1000;
var
  x,y,z:array[0..maxn]of word;
  s,e:array[0..maxm*2]of byte;
  time:array[-1..maxm*2]of extended;
  v:array[1..maxm*2]of boolean;
  n,m,target,i:integer;
  v1,v2,t:extended;
function straight(a,b:byte):extended;
  begin
    straight:=sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b])+sqr(z[a]-z[b]))/v1;
  end;
function arccos(x:real):real;
  begin
    if abs(x)<1e-6 then
      arccos:=pi/2
    else if x>0 then
      arccos:=arctan(sqrt(1-x*x)/x)
    else
      arccos:=pi+arctan(sqrt(1-x*x)/x);
  end;
function turn(a,b,c:byte):extended;
  var
    x1,y1,z1,x2,y2,z2:integer;
  begin
    x1:=x[b]-x[a];y1:=y[b]-y[a];z1:=z[b]-z[a];
    x2:=x[c]-x[b];y2:=y[c]-y[b];z2:=z[c]-z[b];
    turn:=arccos((x1*x2+y1*y2+z1*z2)
          /sqrt(sqr(x1)+sqr(y1)+sqr(z1))/sqrt(sqr(x2)+sqr(y2)+sqr(z2)))
          /v2;
  end;
begin
  time[-1]:=9e99;
  repeat
    read(n,m,target,e[0],v1,v2);
    for i:=1 to n do
      read(x[i],y[i],z[i]);
    for i:=1 to m do begin
      read(s[i*2],e[i*2]);
      s[i*2-1]:=e[i*2];e[i*2-1]:=s[i*2];
    end;

    time[0]:=straight(0,e[0]);
    m:=m*2;for i:=1 to m do time[i]:=9e99;
    fillchar(v,sizeof(v),0);
    n:=0;
    repeat
      for i:=1 to m do
        if not v[i] and (e[n]=s[i]) then begin
          t:=time[n]+turn(s[n],e[n],e[i])+straight(s[i],e[i]);
          if t<time[i] then time[i]:=t;
        end;
      n:=-1;
      for i:=1 to m do
        if not v[i] and (time[i]<time[n]) then n:=i;
      v[n]:=true;
    until e[n]=target;
    writeln(time[n]:0:3);
  until seekeof;
end.