GroupBlog

题意

给定n个点，点1为起点，点2为终点，求点一到点二的所有路径中，求在所有路径中每条路径最大段的最小值

思路

用dijkstra，d[i]表示1到i的路径中最大路段的最小值

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>

using namespace std;

const int N = 209;
double v[N][N] = {};
double d[N];
bool vis[N] = {};
int x[N], y[N];

double dijkstra(int n)
{
    for(int i=1;i<=n;i++)
        d[i] = v[i][1];
    d[1] = 0;
    memset(vis, 0, sizeof(vis));
    vis[1] = true;
    for(int i=1;i<n;i++)
    {
        int mini = 0;
        double min = 99999999;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j] && d[j] < min)
            {
                mini = j; min = d[j];
            }
        }
        vis[mini] = true;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j])
            {
                double mmax = max(min, v[j][mini]);
                if(mmax < d[j])
                    d[j] = mmax;
            }
        }
    }
    return d[2];
}

int main()
{
    int n, T = 1;
    while(cin>>n && n)
    {
        if(T != 1)
            cout<<endl;
        for(int i=1;i<=n;i++)
        {
            cin>>x[i]>>y[i];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
                v[i][j] = v[j][i] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
        }
        cout<<"Scenario #"<<T++<<endl;
        cout<<"Frog Distance = ";
        printf("%.3f\n", dijkstra(n));
    }
}