poj 2253 Frogger （最短路变种，连通图的最长边）

题目

这里的dijsktra的变种代码是我看着自己打的，终于把代码和做法思路联系上了，也就是理解了算法——看来手跟着画一遍真的有助于理解。

#define  _CRT_SECURE_NO_WARNINGS

#include<string.h>

#include<stdio.h>

#include<math.h>

#include<algorithm>

using namespace std;

const int MAXN=;

#define typec double

const typec INF=0x3f3f3f3f*1.0;//防止后面溢出，这个不能太大

bool vis[MAXN];

typec cost[MAXN][MAXN];

typec lowcost[MAXN];

void Dijkstra(int n,int beg)  //连通图的最小边——最短路变种

{

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

    {

        lowcost[i]=INF;vis[i]=false;

    }

    lowcost[beg]=0.0;

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

    {

        typec temp=INF;

        int k=-;

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

        {

            if(!vis[j]&&lowcost[j]<temp)

            {

                temp=lowcost[j];

                k=j;

            }

        }

        vis[k]=true;

        for(int l=;l<n;l++)

        {

            if(!vis[l])

            {

                lowcost[l]=min(max(lowcost[k],cost[k][l]),lowcost[l]);//原来改动在这列，具体可画图求证感知

            }

        }

    }

}

int main()

{

    int n,i,j,id=;

    typec a[MAXN],b[MAXN];

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

    {

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

                cost[i][i]=;

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

        {

            scanf("%lf%lf",&a[i],&b[i]);

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

            {

                cost[i][j]=cost[j][i]=sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j]));

            }

        }

        Dijkstra(n,);

        printf("Scenario #%d\nFrog Distance = %.3lf\n\n",id++,lowcost[]);

    }

    return ;

}