这道题目的题意就纠结了很久,刚开始没有读懂,用Kruskal给过了,后来查解题报告可以用Dijkstra,于是就打算用这个算法写一写,松弛那里一直不知道怎么下手,后来搜了无数份解题报告还是看不懂松弛那里怎么实现的,最后和wjx讨论后才理清了思路,原来一直纠结错了地方,虽然算法用对了但是松弛那里却还紧握着最短路径

分析:首先, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones. 这句话是说,在一条路径中的的最长路必须是所有路径中最长路的最短路这就是Frogger distance

核心代码

for (j=1;j<=n;j++)
{
if(!p[j] && map[k][j]!=INF)
{
if(dist[j]>max(dist[k],map[k][j]))
dist[j]=max(dist[k],map[k][j]);
}
}

#include<stdio.h>

#include<string.h>
#include<math.h>
const int MAXN=300;
const int INF=0x7fffffff;
int map[MAXN][MAXN];
int dist[MAXN];//记录最长的边
int n;
struct Point
{
    int x,y;
}pnt[MAXN];
int max(int a,int b)
{
    return a>b?a:b;
}
int min(int a,int b)
{
    return a<b?a:b;
}
int _dist(Point a,Point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void Dijkstra()
{
   int i,j,k;
   int min;
   int p[MAXN];
   for (i=1;i<=n;i++)
   {
       p[i]=0;
       dist[i]=map[1][i];//1是源点,具体的源点不同
   }
   dist[1]=0;
   p[1]=1;
   for (i=1;i<=n-1;i++)
   {
       min=INF;
       k=0;
       for (j=1;j<=n;j++)
       {
           if(!p[j] && dist[j]<min)
           {
               min=dist[j];
               k=j;
           }
       }
       if(k==0) return ;
       p[k]=1;
       for (j=1;j<=n;j++)
       {
           if(!p[j] && map[k][j]!=INF)
           {
               if(dist[j]>max(dist[k],map[k][j]))
               dist[j]=max(dist[k],map[k][j]);
           }
       }
   }
}
int main()
{
    int cas=1,i,j;
    while(scanf("%d",&n) && n)
    {
        for (i=1;i<=n;i++)
        {
            scanf("%d%d",&pnt[i].x,&pnt[i].y);
        }
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
            {
                if(i==j) map[i][j]=0;
                else map[i][j]=INF;
            }
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++)
            {
                    map[i][j]=_dist(pnt[i],pnt[j]);
            }
        }
        Dijkstra();
        printf("Scenario #%d\n",cas++);
        printf("Frog Distance = %.3f\n\n",sqrt(1.0*dist[2]));
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation