博客

题意

：在出1到2的所有路径中，每一条路都有一个最大的石头距离，在所有路径中这个最大值中的最小值就是答案！

变形1

：dist数组保存的是起点到每一个点的的最大石头距离

int temp = inf;
int now = -1;
for(int j = 1; j <= n; j++){
    if(!vis[j] && dist[j] < temp){
        temp = dist[j];
        now = j;
    }
}

这样按照模板中求dist的最小值就是求的每条路径中的最大值的最小值

变形2：

每次修改dist数组是修改起点到当前点的距离和当前点到下一个点的距离的最大值，这样就和第一个变形联系起来了，所以这样求出来的就是每条路中最大的距离的最小值。

for(int j = 1; j <= n; j++){
            if(!vis[j] && dist[j] > max(dist[now],d(node[now],node[j]))){
                dist[j] = max(dist[now],d(node[now],node[j]));
            }
}

ac代码：提交选择c++

#include<iostream>
#include<stdio.h>
#include<cmath>
#include<cstring>
#include<stack>
#include<algorithm>
#include<queue>
#include<map>
#include<climits>
#define ll long long

using namespace std;
const int inf = INT_MAX;

struct ston{
    int x,y;
}node[210];

double dist[210];
int vis[210];
int n;

double d(ston a,ston b){
    double X = (a.x - b.x) * 1.0;
    double Y = (a.y - b.y) * 1.0;
    return sqrt(X * X + Y * Y);
}

void dijkstra(){
//    for(int i = 1; i <= n; i++)
//        dist[i] = inf;
    fill(dist + 1, dist + n + 1,inf);
    dist[1] = 0;
    for(int i = 1; i <= n; i++){
        int temp = inf;
        int now = -1;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && dist[j] < temp){
                temp = dist[j];
                now = j;
            }
        }
        vis[now] = 1;
        if(now == 2)
            break;
        for(int j = 1; j <= n; j++){
            if(!vis[j] && dist[j] > max(dist[now],d(node[now],node[j]))){
                dist[j] = max(dist[now],d(node[now],node[j]));
            }
        }
    }
}

int main(){
    int t = 1;
    while(~scanf("%d",&n) && n){
        memset(vis,0,sizeof(vis));
        for(int i = 1; i <= n; i++){
            scanf("%d %d",&node[i].x,&node[i].y);
        }
        dijkstra();
        printf("Scenario #%d\n",t++);
		printf("Frog Distance = %.3lf\n\n",dist[2]);
    }
    return 0;
}