POJ. 2253 Frogger （Dijkstra )

题意分析

1. 首先给出n个点的坐标，其中第一个点的坐标为青蛙1的坐标，第二个点的坐标为青蛙2的坐标。给出的n个点，两两双向互通，求出由1到2可行通路的所有步骤当中，步长最大值。
2. 在dij原算法的基础上稍作改动即可。dij求解的是单源最短路，现在求解的是步长最大值，那么更新原则就是，当前的这一步比保存的步如果要大的话，就更新，否则就不更新。
3. 如此求解出来的就是单源最大步骤。

代码总览

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <stack>

#include <vector>

#include <cmath>

#define nmax 205

#define inf 1e8+7

using namespace std;

typedef struct{

    int x,y;

}ston;

ston stone[nmax];

double mp[nmax][nmax];

double shortpath[nmax];

double ans[nmax];

bool visit[nmax];

int n;

double cal(ston a ,ston b)

{

    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );

}

void dij(int s)

{

    int cur = s;

    memset(visit,0,sizeof(visit));

    for(int i = 1;i<=n;++i){shortpath[i] = inf;ans[i]=inf;}

    shortpath[cur] = 0;

    visit[cur] = true;

    int temptag;

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

        double minL  = inf;

        for(int j = 1;j<=n;++j){

            double dist;

            if(!visit[j] && max(shortpath[cur] , mp[cur][j]) < shortpath[j]){

                dist = max(shortpath[cur] , mp[cur][j]);

                shortpath[j] = dist;

            }

            if(!visit[j] && minL>shortpath[j]){

                minL = shortpath[j];

                temptag = j;

            }

        }

        if(minL == inf) return;

        cur = temptag;

        visit[cur] = true;

    }

}

void init()

{

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

        for(int j = 1;j<=n;++j)

            mp[i][j] = inf;

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

        scanf("%d %d",&stone[i].x,&stone[i].y);

    }

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

        for(int j = 1;j<=n;++j){

            if(i!=j){

                mp[i][j] = mp[j][i] = cal(stone[i],stone[j]);

            }

        }

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    int kase  = 1;

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

        init();

        dij(1);

        printf("Scenario #%d\n",kase++);

        printf("Frog Distance = %.3f\n\n",shortpath[2]);

    }

    return 0;

}