竹子战争
来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1301
题目描述
话说茅山道士散功重修已足足九九八十一天，这天子时，月上中天，道观前清辉点点。只听得訇然一声，闭关之处整个炸裂开来，烟雾散尽后，只见茅山道士纤尘不染地立于瓦砾之中，抬头望月，面上一片悲悯之色，喃喃道：“孽缘啊……”
果不其然，一名黑衣剑客从旁窜出，剑尖遥遥指向茅山道士，大喝道：“茅山妖道，我已在此等你多时，多年来的恩恩怨怨，就此了断吧！”言不及毕，左手捏了一个剑诀，便欺身上前，直攻茅山下盘。茅山道士看着黑衣剑客有些稚嫩的剑法，眼中掠过复杂的神色：“不如我们换个地方吧，你若能追得上我，我再和你大战一场！”说完向后纵身一跃，就此隐入竹林之中不知所踪。
黑衣剑客知道茅山是个念旧的人，这次必然是要到竹林中的一处隐秘所在。但黑衣剑客的轻功并不高明，每次只能从一棵竹子顶端跳到水平距离不超过R，高度差不超过D的另一棵竹子顶端，所花的时间为两个顶点间的直线距离除以V。你能帮助黑衣剑客以最快的速度追上茅山道士么？
对于40%的数据 0<N<=20,0<=X,Y<=20
对于100%的数据 0<N<=1000,0<=X,Y<=1000,V>0
输入
第一行是四个整数N、R、D、V，表示竹子的数目、最大水平跳跃距离、最大竖直跳跃距离以及黑衣剑客飞行的速度。
接下来N行每行三个整数X、Y、H，表示每棵竹子的坐标及高度，高度大于0。
你可以假定起点在1，终点在N。
同一坐标可能有不同竹子。
输出
输出文件只有一行，为从1到N的最短时间。保留小数点后三位输出。
如果无法到达终点则输出”No Solution”。
样例输入
3 3 4 4 0 0 1 0 3 5 3 3 1
样例输出
2.500
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> #include <stdio.h> #include <cmath> using namespace std; int n,r,d; int v; float s[1001]; bool dl[1001]={0}; bool pd[1001][1001]; struct f{ int x,y,h; }f[1001]; float work(int a,int b) { if(a==b)return 0; float s=sqrt((f[a].x-f[b].x)*(f[a].x-f[b].x)+(f[a].y-f[b].y)*(f[a].y-f[b].y)); float h1=abs(f[a].h-f[b].h); if(s<=r&&h1<=d) return sqrt(s*s+h1*h1); else return -1; } void search() { int t=0,w=1; int d[5000]={1}; dl[1]=1; s[1]=0; while(t<w) { for(int i=1;i<=n;i++) { if(pd[d[t]][i]==1&&s[d[t]]+work(d[t],i)<s[i]) { s[i]=s[d[t]]+work(d[t],i); if(dl[i]==0) { d[w]=i; dl[i]=1; w++; } } } dl[d[t]]=0; t++; } } int main() { cin>>n>>r>>d>>v; for(int i=1;i<=n;i++) cin>>f[i].x>>f[i].y>>f[i].h; for(int i=1;i<=n;i++) { s[i]=9999; for(int j=1;j<=n;j++) { if(work(i,j)==-1){pd[i][j]=0;} else pd[i][j]=1; } } search(); if(s[n]!=9999)printf("%.3f",s[n]/v); else cout<<"No Solution"; return 0; } |
Subscribe
计数器 9854447
OI 课件=>
OI 课件=>