[ACM] POJ 2253 Frogger （最短路径变形，每条通路中的最长边的最小值）

Description

Input

Output

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

Source

对着题意不长的英文看了好几遍，才明确什么叫 the frog distance . 

有N块石头。1—N。每块石头都有x,y坐标，青蛙一号站在第一块石头上，青蛙二号站在第二块石头上，青蛙一号想要通过这N块石头去找青蛙二号，由于青蛙一号能够踩在不论什么一块石头上，所以从第一块石头到第二块石头有非常多条路径，如果为X，在每一条路径中，都有跳跃范围（即在这条路径中，两块石头之间的最大距离），那么一共同拥有X个跳跃范围。我们要求的就是这X个跳跃范围的最小值。就是the frog distance。   比方有  有两条通路  1(4)5 (3）2 代表1到5之间的边为4,  5到2之间的边为3。那么该条通路跳跃范围（两块石头之间的最大距离）为 4，  还有一条通路 1(6) 4(1) 2 ，该条通路的跳跃范围为6， 两条通路的跳跃范围各自是 4 ，6，我们要求的就是最小的那一个跳跃范围，即4.

边的遍历和点值的更新。这个点值代表的是，从1号石头到第[i]块石头的frog distance。

用floyed算法和dijkstra算法，把更新点值的语句修改一下就能够。

代码：

floyed:

#include <iostream>
#include <cmath>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxNode=210;
double mp[maxNode][maxNode];
int nodeNum;

struct P
{
    int x,y;
}point[maxNode];

double dis(P a,P b)
{
    return sqrt((b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x));
}

void floyed()
{
    for(int k=1;k<=nodeNum;k++)
        for(int i=1;i<=nodeNum;i++)
        for(int j=1;j<=nodeNum;j++)
            mp[i][j]=min(mp[i][j],max(mp[i][k],mp[k][j]));//很多通路中最长边中的最小边
}

int main()
{
    int c=1;
    while(cin>>nodeNum&&nodeNum)
    {
        for(int i=1;i<=nodeNum;i++)
            cin>>point[i].x>>point[i].y;
        for(int i=1;i<=nodeNum;i++)
            for(int j=i+1;j<=nodeNum;j++)
        {
            mp[i][j]=mp[j][i]=dis(point[i],point[j]);
        }
        floyed();
        cout<<"Scenario #"<<c++<<endl;
        cout<<setiosflags(ios::fixed)<<setprecision(3)<<"Frog Distance = "<<mp[1][2]<<endl;
        cout<<endl;
    }
    return 0;
}

#include <iostream>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
const int maxn=210;
const int inf=0x3f3f3f3f;
double mp[maxn][maxn];
double dist[maxn];
bool vis[maxn];
int n;

struct  P
{
    int x,y;
}point[maxn];

double dis(P a,P b)
{
    return sqrt((b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x));
}

void dijkstra(int start)
{
    memset(vis,0,sizeof(vis));
    //memset(dist,inf,sizeof(dist));
    for(int i=1;i<=n;i++)
        dist[i]=inf;
    dist[start]=0;
    for(int i=1;i<=n;i++)
    {
        int MinNum,Min=inf;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&dist[j]<Min)
        {
            MinNum=j;
            Min=dist[j];
        }
        vis[MinNum]=1;
        for(int j=1;j<=n;j++)
            dist[j]=min(dist[j],max(dist[MinNum],mp[MinNum][j]));//dis[j]为从一号石头到第j号石头全部通路中最长边中的最小边
    }
}

int main()
{
    int c=1;
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++)
            cin>>point[i].x>>point[i].y;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                mp[i][j]=mp[j][i]=dis(point[i],point[j]);
            }
        dijkstra(1);
        cout<<"Scenario #"<<c++<<endl;
        cout<<setiosflags(ios::fixed)<<setprecision(3)<<"Frog Distance = "<<dist[2]<<endl;
        cout<<endl;
    }
    return 0;
}