題目大意
有兩只青蛙赞咙，分別在兩個石頭上，青蛙GG想跳到青蛙MM所在的石頭上糟港。
它有兩種跳法：
1攀操、直接跳到MM的石頭上
2、先跳到其他石頭上秸抚，再從其他石頭跳到MM所在石頭上速和；
問題是：求青蛙從GG到MM的所有路徑中最小的Frog Distance歹垫，即路徑中所GG跳的最大距離（最短路徑中的最長距離）；
例如颠放，如果從GG到MM最短路徑跳的幾段為2县钥，5，6慈迈，4，則輸出的就是6省有。
這題可以用Dijkstra解決
輸入分析
2 //石頭個數(shù) （個數(shù)為0時結(jié)束程序）
0 0 //GG的坐標(biāo)
3 4 //MM的坐標(biāo)
3 //石頭個數(shù)
17 4 //GG的坐標(biāo)
19 4 //MM的坐標(biāo)
18 5 //第三行后都是空石頭的坐標(biāo)
0
輸出分析
Scenario #1
Frog Distance = 5.000 //輸出一個小數(shù)（保留三位）
//空行痒留，每個輸出后都要有
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數(shù)組存圖 dis存最短距離
bool vis[222]; //判斷是否此點已查過
int x[222], y[222]; //存坐標(biāo)，也可用結(jié)構(gòu)體
void ini() //初始化
{
memset(vis, false, sizeof(vis));
for(int i = 1; i < n; i++)
{ // 從1開始蠢沿，因為沒從一開始筆者挖了40發(fā)伸头。。舷蟀。各種改恤磷。。野宜。
// 從1開始是因為dijkstra的算法要求
dis[i] = INF;
}
}
void dijs()
{
vis[0] = true; //標(biāo)記0點已查過
int l=0; //存上一輪最小值的位置
for (int i = 0; i < n-1; i++)
{
int k; //保存下標(biāo)
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，不符合匈子，直接結(jié)束
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)); //清空數(shù)組
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的坐標(biāo)在GG的坐標(biāo)后一個輸入
{
dx = x[i] - x[j];
dy = y[i] - y[j];
w = sqrt(dx*dx + dy*dy);
edge[i][j] = edge[j][i] = w; //兩點間的距離才是每條邊的權(quán)值：犹ァ！
}
}
dijs();
printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++k, dis[1]);
}//一定要是兩個 “ \n ”；⒍亍游岳！
return 0;
}
坑點
1、距離數(shù)組初始化的時候一定要將源點標(biāo)記為0
2其徙、權(quán)值是兩點間距離
3胚迫、每一個輸出距離之間空一行要兩個回車鍵
