题目大意
有两只青蛙，分别在两个石头上，青蛙GG想跳到青蛙MM所在的石头上。
它有两种跳法：
1、直接跳到MM的石头上
2、先跳到其他石头上，再从其他石头跳到MM所在石头上；
问题是：求青蛙从GG到MM的所有路径中最小的Frog Distance，即路径中所GG跳的最大距离（最短路径中的最长距离）；
例如，如果从GG到MM最短路径跳的几段为2，5，6，4，则输出的就是6。
这题可以用Dijkstra解决
输入分析
2 //石头个数 （个数为0时结束程序）
0 0 //GG的坐标
3 4 //MM的坐标
3 //石头个数
17 4 //GG的坐标
19 4 //MM的坐标
18 5 //第三行后都是空石头的坐标
0
输出分析
Scenario #1
Frog Distance = 5.000 //输出一个小数（保留三位）
//空行，每个输出后都要有
Scenario #2
Frog Distance = 1.414
代码分析
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <iostream>
using namespace std;
const int INF = 99999999;
int n;
float edge[222][222], dis[222]; // edge数组存图 dis存最短距离
bool vis[222]; //判断是否此点已查过
int x[222], y[222]; //存坐标，也可用结构体
void ini() //初始化
{
memset(vis, false, sizeof(vis));
for(int i = 1; i < n; i++)
{ // 从1开始，因为没从一开始笔者挖了40发。。。各种改。。。
// 从1开始是因为dijkstra的算法要求
dis[i] = INF;
}
}
void dijs()
{
vis[0] = true; //标记0点已查过
int l=0; //存上一轮最小值的位置
for (int i = 0; i < n-1; i++)
{
int k; //保存下标
float minx = INF;
for (int j = 1; j < n; j++)
{
if (!vis[j])
{
if(max(dis[l], edge[j][l]) < dis[j]) //判断是否为最短路径中的最大距离
dis[j] = max(dis[l], edge[j][l]);//保存此最短路径中的最大距离
if(minx > dis[j])
{
minx = dis[j]; //存点，进行下一轮搜索
k = j;
}
}
}
if(k == 1) return; // 如果点为1，不符合，直接结束
l = k;
vis[k] = true;
}
}
int main()
{
int k = 0;
float dx, dy, w;
while(scanf("%d", &n)!=EOF && n!=0)
{
ini();
memset(x, 0, sizeof(x)); //清空数组
memset(y, 0, sizeof(y));
for (int i = 0; i < n; i++)
{
cin >> x[i] >> y[i];
for (int j = i-1; j >= 0; j--) //MM的坐标在GG的坐标后一个输入
{
dx = x[i] - x[j];
dy = y[i] - y[j];
w = sqrt(dx*dx + dy*dy);
edge[i][j] = edge[j][i] = w; //两点间的距离才是每条边的权值！！
}
}
dijs();
printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++k, dis[1]);
}//一定要是两个 “ \n ”！！
return 0;
}
坑点
1、距离数组初始化的时候一定要将源点标记为0
2、权值是两点间距离
3、每一个输出距离之间空一行要两个回车键
网友评论