POJ-2253 Frogger

本文主要是介绍POJ-2253 Frogger，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：青蛙想从一个点跳到另一个点，中途可以经过其他点。求起点到终点间所有路径中相邻两点最大距离的最小值。

解：所有最短路算法都可以，这里练了一下Floyd。将两点间最短路改成走到这一点上长度最小的最大值（好绕哦）。先计算出有直接边的距离，然后枚举每个点进行松弛，由于过程中要求最大值，所以没有直接边的初始化为0。

代码：

 1 #include<stdio.h>
 2 #include <algorithm>
 3 #include <queue>
 4 #include <math.h>
 5 using namespace std;
 6 #define ll long long
 7 #define maxx 205
 8 #define inf 0x7fffffff
 9 //#define int long long
10 struct edge{
11     int u,v,w;
12     int nxt;
13 }e[maxx*2];
14 int head[maxx]={0},cnt=0;
15 void add(int u,int v,int w){
16     e[++cnt].u=u;
17     e[cnt].v=v;
18     e[cnt].w=w;
19     e[cnt].nxt=head[u];
20     head[u]=cnt;
21 }
22 int x[maxx],y[maxx];
23 double mp[maxx][maxx];
24 int n,cnt1=1;
25 void floyd(){
26     for(int k=1;k<=n;k++)
27         for(int i=1;i<=n;i++)
28             for(int j=1;j<=n;j++)
29                 mp[i][j]=min(mp[i][j],max(mp[i][k],mp[k][j]));
30 }
31 double distance(double x1,double x2,double y1,double y2){
32     return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
33 }
34 signed main() {
35     while(~scanf("%d",&n)){
36         if(n==0)
37             break;
38         memset(mp,0,sizeof mp);
39         for(int i=1;i<=n;i++)
40             scanf("%d%d",&x[i],&y[i]);
41         for(int i=1;i<=n;i++)
42             for(int j=1;j<=n;j++)
43                 mp[i][j]=distance(x[i],x[j],y[i],y[j]);
44         floyd();
45         printf("Scenario #%d\n",cnt1++);
46         printf("Frog Distance = %.3lf\n\n",mp[1][2]);
47     }
48     return 0;
49 }

//以及这题保留8位小数会WA，但像样例一样保留3位就对了，怪耶。

这篇关于POJ-2253 Frogger的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！