Description
一只叫Freddy的青蛙蹲坐在湖中的一块石头上。突然他发现一只叫Fiona的青蛙在湖中的另一块石头上。Freddy想要跟Fiona约会,但由于湖水太脏,他不想游泳过去而是跳过去找Fiona。
很不幸,Fiona所在的石头距离他有点远,甚至超出了他的跳跃能力。然而Freddy注意到湖中还有一些其他的石头。这些石头也许会将这个很长的跳跃距离化成若干个短的跳跃距离。
我们定义“青蛙距离”为Freddy跳到Fiona那里所需要的若干次跳跃中最长的那一次。现在给你Freddy,Fiona,以及湖中其他石头的坐标,让你求出最短的“青蛙距离”。
Input
输入有可能是多组测试数据。每组数据的第一行有一个整数n(2<=n<=200),表示湖中一共有多少块石头。接下来的n行,每一行有两个整数xi,yi(0 <= xi,yi <= 1000),表示第i块石头的坐标。第1块石头的坐标是Freddy所在的位置,第二块石头的坐标是Fiona所在的位置,其他的石头上都没有青蛙。当输入n=0的时候,程序结束。
Output
对于每一组测试数据,先输出一行"Scenario #x",然后在下一行输出"Frog Distance = y"。其中x表示当前是第几组测试数据,y为该组数据的最小“青蛙距离”。每两组测试数据之间输出一个空行。
Sample Input
2
0 0
3 4
3
17 4
19 4
18 5
0
Sample Output
Scenario #1
Frog Distance = 5.000
Scenario #2
Frog Distance = 1.414
这个题目的意思太难理解了,我开始还以为是从第一个点到第二个点之间的最短距离,可结果错了。原来是求从第
一个节点到第二个节点的生成的最小二叉树中的最大长度。好了不罗嗦了,直接看代码吧!
#include <stdio.h>
#include <string.h>
#include <math.h>
#define INFINITE 999999999.9
#define N 201
double getLength(double x1, double y1, double x2, double y2)
{
/*求两点之间的距离*/
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double Dijkstra(double map[N][N], int v, int n, int m)
{
int i;
int s[N]; //s[i]=0代表顶点未入S集,s[i]=1表示顶点i已入S集
double dist[N]; //dist[i]表示当前已知的从源点到顶点i的最短路径的长度
double min, max;
int u;
for(i = 0; i < n; i++)
{
dist[i] = map[v][i];
s[i] = 0;
}
s[v] = 1; //初始时v进入s集
dist[v] = 0;
max = 0;
u = v;
while(u != m)
{
min = INFINITE;
for(i = 0; i < n; i++) //求源点u到其他顶点i的最短距离
{
if(!s[i] && (dist[i] < min))
{
u = i;
min = dist[i];
}
}
if(min > max) max = min;
s[u] = 1; //将u加入s集
for(i = 0; i < n; i++)
{
if(!s[i] && (map[u][i] < INFINITE) && (map[u][i] < dist[i]))
{
dist[i] = map[u][i];
}
}
}
return max;
}
int main()
{
int i, j, k;
int n, count = 0;
double map[N][N];
int x[N], y[N];
while(scanf("%d", &n) && n)
{
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
map[i][j] = INFINITE;
}
scanf("%d %d", &x[i], &y[i]);
}
for(i = 0; i < n; i++)
{
/*建图*/
for(j = 0; j < n; j++)
{
map[i][j] = getLength(x[i], y[i], x[j], y[j]);
}
}
printf("Scenario #%d\n", ++count);
printf("Frog Distance = %.3lf\n\n", Dijkstra(map, 0, n, 1));
}
return 0;
}
分享到:
相关推荐
北大POJ1062-Expensive dowry【dijkstra】 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
北大POJ2253-Frogger【Floyd】 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ中级-基本算法 解题报告+AC代码
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
北大POJ3273-Monthly Expense POJ3273-Monthly Expense