点击打开链接hdu 1245
思路:最短路+floyd
分析:
1 题目讲的是有一个湖100x100这个人刚开始在一个直径为15的圆心在原点的园内,然后要通过跳跃的方式问我们他是否能够到达岸边。如果可以求出最短的路径和步数
2 很明确就是最短路问题。但是这个时候问题来了,起点和终点是在哪里,所以我们采用的是将原点作为起点,岸边做为终点。知道了起点和终点,我们就可以求最短路,但是这个时候会碰到另外一个问题,边的长度。对于这个问题,我们是采取的方法是将这些点分成三类。1类:起点 2类:终点 3类:其它点 ,那么我们就可以分别对这三类的点求出它和其它点的距离。
注意事项:
1 输入的数据中,点的范围可能会在园内或在湖外,所以在输入的时候要判断点是否合法。
2 这一题精度要求很严格,一些比较之类的要注意精度问题
3 注意n = 0 的情况,这里如果n = 0,但是d > 42.5 是可以跳出去的。但是只要有乌龟,这个人就必须通过踩在乌龟上面跳出去,所以n = 0是比较特殊的。
4 n不大所以什么方法都可以做
5 求所需几步的时候利用一个setp[][]数组,首先初始户为0然后将可以到达的点标记为1,最后只要在更新dis[][]的时候更新即可。
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define MAXN 110
#define INF 0xFFFFFFF
#define eps 1e-12
int n;
double d;
double dis[MAXN][MAXN];
int setp[MAXN][MAXN];
struct Point{
int x;
int y;
}p[MAXN];
/*初始话边*/
void init(){
memset(setp , 0 , sizeof(setp));/*初始话为0*/
/*第三类的点*/
for(int i = 2 ; i < n ; i++){
for(int j = 2 ; j < n ; j++){
double tmp_x = (p[i].x-p[j].x)*(p[i].x-p[j].x);
double tmp_y = (p[i].y-p[j].y)*(p[i].y-p[j].y);
double tmp = sqrt(tmp_x + tmp_y);
if(tmp-d <= eps){
dis[i][j] = tmp;
setp[i][j] = 1;
}
else
dis[i][j] = INF;
}
dis[i][i] = 0;
}
/*第一类点*/
dis[1][1] = 0;
dis[1][n] = dis[n][1] = INF;
for(int i = 2 ; i < n ; i++){
double tmp = sqrt((p[i].x)*(p[i].x)*1.0+(p[i].y)*(p[i].y)*1.0);
if(tmp-7.5-d <= eps){/*注意要减去7.5*/
dis[1][i] = dis[i][1] = tmp-7.5;
setp[1][i] = setp[i][1] = 1;
}
else
dis[1][i] = dis[i][1] = INF;
}
/*第二类点*/
dis[n][n] = 0;
for(int i = 2 ; i < n ; i++){
int a = 50-abs(p[i].x);
int b = 50-abs(p[i].y);
int min = a < b ? a : b;
if(min-d <= eps){
dis[i][n] = dis[n][i] = min;
setp[i][n] = setp[n][i] = 1;
}
else
dis[i][n] = dis[n][i] = INF;
}
}
/*floyd算法*/
void floyd(){
for(int k = 1 ; k <= n ; k++){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
if(dis[i][j]-(dis[i][k]+dis[k][j]) >= eps){
dis[i][j] = dis[i][k]+dis[k][j];
setp[i][j] = setp[i][k] + setp[k][j];/*更新数组*/
}
}
}
}
}
int main(){
int a , b , j;
while(scanf("%d %lf" , &n , &d) != EOF){
j = 2;/*默认1为起点,j从2开始*/
for(int i = 0 ; i < n ; i++){
scanf("%d%d" , &a , &b);
if(abs(a) < 8 && abs(b) < 8 || abs(a) > 50 && abs(b) > 50)/*如果不合法就跳过*/
continue;
p[j].x = a;
p[j++].y = b;
}
n = j;
if(!n){/*判断n是否为0*/
if(d-42.5 >= eps)
printf("42.50 1\n");
else
printf("can't be saved\n");
continue;
}
init();
floyd();
if(dis[1][n] != INF)/*是否可以跳出去*/
printf("%0.2lf %d\n" , dis[1][n] , setp[1][n]);
else
printf("can't be saved\n");
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码