POJ 2253 Frogger（最短路的最小权值）

Frogger

解题思路：
有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.

//#include<bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace  std;
const int INF = 0x3f3f3f3f;
struct Node {
    int x, y;
} p[205];
double mp[205][205];
double dis[205];
bool vis[205];
int n;
double  dir(Node a, Node b)
{
    return sqrt((b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));
}
void dij(int k)
{
    for (int i = 1; i < 205; i++)vis[i] = false;for (int i = 1; i <= n; i++)dis[i] = INF;dis[k] = 0;for (int i = 1; i <= n; i++) {
    int minnum, minn = INF;for (int j = 1; j <= n; j++) {
    if (!vis[j] && dis[j] < minn) {
    minnum = j;minn = dis[j];}}vis[minnum] = true;for (int j = 1; j <= n; j++) {
    dis[j] = min(dis[j], max(dis[minnum], mp[minnum][j]));}}
}
int  main()
{
    int c = 1;while (cin >> n && n) {
    for (int i = 1; i <= n; i++) {
    cin >> p[i].x >> p[i].y;}for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
    mp[i][j] = mp[j][i] = dir(p[i], p[j]);}}dij(1);printf("Scenario #%d\nFrog Distance = %.3f\n", c, dis[2]);printf("\n");c++;}return 0;
}

学习记录