POJ2253 Frogger（最短路）

题目链接。

题意：

从0号点，到1号点，找一条能通过的路，使得这条路中的最大的边，比其它所有可能的路中的边都小。

分析：

这题就是按着dijkstra写，写着写着觉得像是prim了。

其中d[n]表示从0出发到达该点的某条路中的最大边，且比其它可能的路中的都小。

从d[i]到d[j], 就是要用 max(d[i], G[i][j]) 去更新 d[j] 。

注意：

输出时要用 %.3f 不能用 %.3lf.

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <algorithm>

#include <cmath>

#include <string>

#include <map>

#include <cmath>

using namespace std;

const int maxn = ;

const double INF = 1e60;

int n;

double G[maxn][maxn], d[maxn];

struct Pos {

    int x, y;

}num[maxn];

double calc(int i, int j) {

    return (sqrt(pow((double)num[i].x-num[j].x, )+pow((double)num[i].y-num[j].y, )));

}

double dijkstra() {

    bool vis[maxn];

    memset(vis, false, sizeof(vis));

    for(int i=; i<n; i++) {

        d[i] = G[][i];

    }

    d[] = ;

    vis[] = true;

    for(int i=; i<n-; i++) {

        double m = INF; int x;

        for(int y=; y<n; y++) if(!vis[y] && m >= d[y]) m = d[x=y];

        vis[x] = true;

        for(int y=; y<n; y++){

            if(!vis[y]) {

                double maxx = max(d[x], G[x][y]);

                if(d[y] > maxx) d[y] = maxx;

            }

        }

    }

    return d[];

}

int main() {

    int cnt = ;

    while(scanf("%d", &n) == ) {

        if(n == ) break;

        for(int i=; i<n; i++) scanf("%d%d", &num[i].x, &num[i].y);

        for(int i=; i<n; i++) {

            for(int j=; j<i; j++) {

                G[i][j] = G[j][i] = calc(i, j);

            }

            G[i][i] = ;

        }

        printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++cnt, dijkstra());

    }

    return ;

}