poj 2253 (dijkstra 变形)

http://poj.org/problem?id=2253

一个池塘中分布着n块可供青蛙跳跃的石头，坐标分别为sto[i].x和sto[i].y，给出Freddy和Fiona站的石头，

问Freddy想借助这些石头，跳去Fiona那，它的跳跃距离至少是多少？


最短路的变形啊 松弛方程 dis[j]=max(dis[k],map[k][j]);

为什么松弛方程是上面那样呢？》首先我们回忆一下如果dis[j]>dis[k]+map[k][j]

,则更新其值是丛原点到j点的最短距离，那么在此

dis[j]=max(dis[k],map[k][j])表示借助中间点跳的话，要跳的j点，则在路径中最长粗条dia[j];

 #include<stdio.h>
#define max 999999
#define N 250
#include<math.h>
double dis[N],min,ans,map[N][N];
int vis[N],n;
struct node
{
    int x;
    int y;

}p[N];
double max1(double a,double b)
{
    return a>b?a:b;
}
void init()
{
    int i,j;
    for(i=0;i<=n;i++)
    {
        dis[i]=max;
        vis[i]=0;
        for(j=0;j<=n;j++)map[i][j]=max;

    }
    ans=0;
}
void search(int x)
{
  int i,j,k,min;
    vis[x]=1;
    for(i=0;i<n;i++)
    {
        dis[i]=map[x][i];
    }

    dis[x]=0;
    for(i=1;i<n;i++)
    {
        min=max;
        for(j=0;j<n;j++)
        {
            if(min>dis[j]&&vis[j]==0)
            {
                min=dis[j];
                k=j;
            }
        }

        vis[k]=1;
        
        for(j=0;j<n;j++)//松弛方程
        {
            if(map[k][j]!=max&&!vis[j]&&dis[j]>max1(dis[k],map[k][j]))
            dis[j]=max1(dis[k],map[k][j]);
        }
    }
}
int main()
{
    int l=0,i,j;
    while(scanf("%d",&n),n)
    {
        l++;
        init();
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
        }
        for(i=0;i<n-1;i++)
        {
            for(j=i+1;j<n;j++)
            {
                double a=(p[i].x-p[j].x)*(p[i].x-p[j].x)*1.0;
                double b=(p[i].y-p[j].y)*(p[i].y-p[j].y)*1.0;
               map[j][i]= map[i][j]=sqrt(a+b);

            }
        }
        search(0);
        printf("Scenario #%d\n",l);
        printf("Frog Distance = %.3f\n\n",dis[1]);
    }
}