首页 > 代码库 > POJ 2253 Frogger
POJ 2253 Frogger
题目链接：
poj.org/problem?id=2253
题目大意：
Freddy Frog 坐在湖中的一个石头上， 突然的他注意到 Fiona Frog 坐在另一个石头上， Freddy Frog 要去拜访 Fiona Frog ， 但是水很脏，而且有游客的防晒霜漂上面， 为了避免游泳过去他只能跳过去。
不幸的是Fiona 所在的石头不在他跳跃的范围内，因此他只能跳跃几个其他的石头到达 Fiona 所在的石头， 这个青蛙的跳跃有个极大的距离 和 极小距离, 明显的 在他跳跃的路上， 最长距离不能超过他的跳跃极限。
给你所有石头在湖里的坐标， 你的任务是计算 两个人所在石头的距离。
输入：
第一行 一个 n 代表石头的个数， 第一个石头 Freddy 的位置,第二个石头 Fiona 的位置, 其余的n-2个石头是空的， 给你每个点的坐标， 要求的是找出 一条路径， 要你求这个路上的两个石头的最长距离，在所有路径中最短。
题目分析：
这道题目其实就是最短求最大边， 以前有做过此类题目。 运用SPFA 就直接写了
注意： 提交的时候请用 C++ 别用G++
#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>#include <cstring>#include <cmath>using namespace std;#define INF 0xfffffff#define maxn 300struct Point{ double x, y;};double Len(Point A, Point B){ return sqrt( (A.x-B.x) * (A.x-B.x) + (A.y-B.y)*(A.y-B.y) );}int n;double dist[maxn];double G[maxn][maxn];bool vis[maxn];double Spfa(){ int P = 1; queue<int> Q; Q.push(P); while( !Q.empty() ) { P = Q.front(); Q.pop(); vis[P] = false; for(int i=1; i<=n; i++) { if(dist[i] > max(dist[P],G[P][i]) ) { dist[i] = max(dist[P],G[P][i]); if( !vis[i] ) { vis[i] = true; Q.push(i); } } } } return dist[2];}void Init(){ for(int i=1; i<=n; i++) { dist[i] = INF; vis[i] = false; for(int j=1; j<=n; j++) G[i][j] = INF; } dist[1] = 0;}int main(){ Point P[maxn]; int cas = 1; while(scanf("%d", &n), n) { Init(); for(int i=1; i<=n; i++) { scanf("%lf%lf",&P[i].x,&P[i].y); } for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { G[i][j] = Len(P[i],P[j]); G[j][i] = G[i][j]; } } double ans = Spfa(); printf("Scenario #%d\n",cas ++); printf("Frog Distance = %.3lf\n\n", ans); } return 0;}
POJ 2253 Frogger
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。