NOIp倒计时还有66小时.
祝大家取得好成绩.[/color]
此题只需注意只能由坐标高处下落至坐标低处，预处理+dijkstra即可AC
题目:智捅马蜂窝
状态:[color=green] Accepted [/color]
测评机： Xeost[5]
得分： 100分
提交日期： 2010-11-17 15:50:00
有效耗时： 1250毫秒
测试结果1: [color=green]通过本测试点|有效耗时172ms [/color]
测试结果2: [color=green]通过本测试点|有效耗时47ms [/color]
测试结果3: [color=green]通过本测试点|有效耗时47ms [/color]
测试结果4: [color=green]通过本测试点|有效耗时47ms [/color]
测试结果5: [color=green]通过本测试点|有效耗时156ms [/color]
测试结果6: [color=green]通过本测试点|有效耗时156ms [/color]
测试结果7: [color=green]通过本测试点|有效耗时157ms [/color]
测试结果8: [color=green]通过本测试点|有效耗时156ms [/color]
测试结果9: [color=green]通过本测试点|有效耗时156ms [/color]
测试结果10: [color=green]通过本测试点|有效耗时156ms [/color]
Const maxn=100;
Var adj:array[0..maxn,0..maxn]of extended;
xx,yy:array[0..maxn]of longint;
path:array[0..maxn]of extended;
mark:array[0..maxn]of integer;
min:extended;
mini:longint;
i,j,k,m,n,v,f,x,y:longint;
dis,time:extended;
{main}
Begin
readln(n,v);
for i:=1 to n do
for j:=1 to n do
adj[i,j]:=maxint;
for i:=1 to n do
begin
readln(x,y,f);
xx[i]:=x;
yy[i]:=y;
if f=0 then continue;
dis:=sqrt(sqr(xx[i]-xx[f])+sqr(yy[i]-yy[f]));
time:=dis/v;
adj[i,f]:=time;
adj[f,i]:=time;
end;
for i:=1 to n do
for j:=i+1 to n do
begin
if xx[i]<>xx[j] then continue;
dis:=abs(yy[i]-yy[j]);
if dis=0 then continue;
time:=sqrt(dis/5);
if (yy[i]>yy[j])and(adj[i,j]>time) then adj[i,j]:=time;
if (yy[i]<yy[j])and(adj[j,i]>time) then adj[j,i]:=time;
end;
for i:=2 to n do
begin
mark[i]:=2;
path[i]:=maxint;
end;
mark[1]:=1;
path[1]:=0;
while true do
begin
min:=maxint;
for i:=1 to n do
begin
if mark[i]<>1 then continue;
if path[i]<min then
begin
min:=path[i];
mini:=i;
end;
end;
if mini=n then
begin
writeln(path[n]:0:2);
halt;
end;
mark[mini]:=0;
for i:=1 to n do
begin
if mark[i]=0 then continue;
dis:=adj[mini,i]+min;
if dis<path[i] then
begin
mark[i]:=1;
path[i]:=dis;
end;
end;
end;
End.