讨论 / AC200题留念——L.Lawliet
L.Lawliet 2010-11-17 17:03:00
点我顶贴 收藏 删除
[color=red]AC200题,排名进入前50!

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.

#1 L.Lawliet@2010-11-17 17:02:00
回复 删除
顶上去~
#2 L.Lawliet@2010-11-17 17:02:00
回复 删除
ding
#3 L.Lawliet@2010-11-17 17:03:00
回复 删除
?为什么顶不到150前面
#4 159753abclife@2015-10-29 21:59:29
回复 删除
顶+赞
#5 159753abclife@2015-10-29 22:00:11
回复 删除
顶+赞.
#6 159753abclife@2015-10-29 22:00:18
回复 删除
顶+赞..
#7 159753abclife@2015-10-29 22:00:23
回复 删除
顶+赞顶+赞
#8 159753abclife@2015-10-29 22:00:30
回复 删除
顶+赞 顶+赞 顶+赞
#9 159753abclife@2015-10-29 22:00:37
回复 删除
狂顶 狂赞
#10 tchwr@2015-10-30 12:51:30
回复 删除
给你1*2^0+1*2^1+1*2^2+1*2^3+1*2^4+1*2^5+1*2^6+1*2^7+1*2^8+1*2^9+1*2^10+……+1*2^n个赞
查看更多回复
提交回复