首页 > 代码库 > POJ 2253 (Frogger)

POJ 2253 (Frogger)

2024-07-08 05:52:53   231人阅读

题目大意：

    青蛙A在一块石头上想通过一系列的跳跃跳到青蛙B的石头上，这里会给出池塘里所有石头的坐标，其中第一个给出的是青蛙A的石头坐标，第二个给出的坐标上衣青蛙B的坐标，这里让你求所有可能的路径中最小的frog distance。 这里的frog distance的定义是一条路径跳跃最大的距离。

举个例子：17 4 、19 4 、18 5

    这是青蛙A的坐标是17 4,青蛙B 的坐标是 19 4.另一块可以跳跃的石头坐标是18 5.

所以青蛙A到青蛙B的路径可以有两条17 4—>19 4  这个路径的frog distance（最大的跳跃路径）是 2。 另一条的路径是 17 4—>18 5 —>19 4 的跳跃距离是1.414、       1.414 ，所以青蛙A的最大跳跃路径是1.414 。  所以所有路径的最小 frog distance 是1.414 。 

 

 解题思路：

    简单的pirm算法。  求不完全的最小生成树青蛙A-青蛙B的最小生成树。  求出最小生成树说明每段的跳跃距离都是最小的，最后输出最小生成树的最大的权值即可！

 

今天学到了一个小知识：

fabs里的数必须是浮点数，abs里的数是整形。可以通过编译器但OJ会编译错误，我是有多水，今天才知道。 还有就是sqrt里面的也是double，如果是整形的话可以在函数里*1.0或者+0.0  都可以。

 

代码：

  1 #include <algorithm>  2 #include <iostream>  3 #include <sstream>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cstdio>  7 #include <string>  8 #include <bitset>  9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {0,-1,0,1}; 25 const int d1y[]= {-1,0,1,0}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33     freopen("data.in","rb",stdin); 34     freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 struct Node 38 { 39     double x,y; 40 }node[520]; 41 int n; 42 double lowcost[520],map[520][520]; 43 double m; 44 double minn; 45 int vis[520]; 46 void prim() 47 { 48     int i,j,k; 49     minn=-1; 50     for(i=1;i<=n;i++) 51     { 52         lowcost[i]=map[1][i]; 53         vis[i]=0; 54     } 55     vis[1]=1; 56     for(i=1;i<=n-1;i++) 57     { 58         m=INF; 59         for(j=1;j<=n;j++) 60         { 61             if (lowcost[j]<m&&!vis[j]) 62             { 63                 k=j; 64                 m=lowcost[j]; 65             } 66         } 67         vis[k]=1; 68         if (minn<m) 69            minn=m; 70         if (k==2) 71             break; 72         for(j=1;j<=n;j++) 73         { 74             if (lowcost[j]>map[k][j]&&!vis[j]) 75                 lowcost[j]=map[k][j]; 76         } 77     } 78     return ; 79 } 80 int main() 81 { 82     int cas=1; 83     while(scanf("%d",&n)&&n) 84     { 85         int i,j; 86         for(i=1;i<=n;i++) 87         { 88             scanf("%lf%lf",&node[i].x,&node[i].y); 89         } 90         for(i=1;i<=n;i++) 91             for(j=1;j<=n;j++) 92                 map[i][j]=INF; 93         for(i=1;i<=n;i++) 94             for(j=1;j<=n;j++) 95             { 96                 map[i][j]=sqrt(fabs(node[j].x-node[i].x)*fabs(node[j].x-node[i].x)+fabs(node[j].y-node[i].y)*fabs(node[j].y-node[i].y))*1.000; 97             } 98         prim(); 99         printf("Scenario #%d\n",cas++);100         printf("Frog Distance = %.3f\n\n",minn);101     }102     return 0;103 }
View Code

 


联系
我们