POJ - 2253 Frogger(Dijkstra变形题)

时间:2023-11-10 19:47:20

题意:

题目撰写者的英语真是艰难晦涩,看了别人题解,才知道这题题意。

两个forger 一个froger 要蹦到另外一个froger处,他们的最短距离是这样定义的 :

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.

即为 :两个石头之间的frog distance就是在这两个石头之间的所有路径中最大跳(necessary jump range)最小的。 (以上引自aowarmen's blog)

题目要我们求解的frog distance和dijksta算法中的最短路径距离不是同一个概念。

分析:

理解了题意之后,我们把Dijsktra中的松弛条件改成:

dist[i] = max( dist[u],edge[u][i])  //u为某一中间节点,dist[i]表示源点到结点i的距离  (以上摘自Eucalyptus

同时,我们可以优化距离的开根号运算,两点之间的距离定义改成:欧几里德距离的平方和。

这样一来,我们只需要对结果开根号即可,节省中间的运算时间。

提交时请不要用g++,要用c++编译器,同样的代码,我用G++提交时总是WA

代码:

优先队列实现的Dijkstra模板,只要修改对应的松弛条件即可。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
#define maxn 201
#define inf 0x3f3f3f3f
#define eps 0.0001
typedef pair<double,int> P;
double max(double a,double b){
return (a>b?a:b);
}
struct points {
int x, y;
points(int xi,int yi){ x=xi,y=yi;}
points(){x=0,y=0;}
}; points nodes[maxn];
double map[maxn][maxn];
double dist[maxn];
double cal_dist(points a,points b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void init(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map[i][j]=cal_dist(nodes[i],nodes[j]);
map[j][i]=map[i][j];
}
}
} void dijkstra(int s,int n){
priority_queue<P,vector<P>,greater<P> > Q;
bool visited[maxn];
memset(visited,0,sizeof(visited));
for(int i=1;i<=n;i++)
dist[i]=inf;
dist[s]=0.0;
Q.push(P(0.0,s)); while(!Q.empty()){
int v=Q.top().second;
Q.pop();
if(visited[v]) continue;
visited[v]=true;
for(int i=1;i<=n;i++){
double local_max=max(dist[v],map[v][i]);
if(dist[i]-local_max>eps){
dist[i]=local_max;
Q.push(P(local_max,i));
}
}
}
}
int main(){
//freopen("in.txt","r",stdin);
int cases=0,n;
while(scanf("%d",&n)!=EOF && n){
cases++;
for(int i=1;i<=n;i++)
scanf("%d %d",&nodes[i].x,&nodes[i].y);
init(n);
dijkstra(1,n);
printf("Scenario #%d\n",cases);
printf("Frog Distance = %.3lf\n\n",sqrt(dist[2]));
}
}

普通方法实现的Dijkstra算法

#include<iostream>
#include<cstdio>
#include<string.h>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
#define maxn 210
#define inf 0x3f3f3f3f
typedef pair<double,int> P;
double max(double a,double b){
return (a>b?a:b);
}
struct point {
double x, y;
point(double xi,double yi){ x=xi,y=yi;}
point(){x=0,y=0;}
}; point nodes[maxn];
double map[maxn][maxn];
double dist[maxn];
double cal_dist(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void init(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) map[i][j]=0.0;
else
map[i][j]=cal_dist(nodes[i],nodes[j]);
map[j][i]=map[i][j];
}
}
} void dijkstra(int s,int n){
bool visited[maxn];
memset(visited,0,sizeof(visited));
visited[s]=true;
for(int i=1;i<=n;i++)
dist[i]=map[s][i];
dist[s]=0.0;
for(int i=1;i<=n;i++){
double min=inf;
int u=0;
for(int j=1;j<=n;j++)
if(!visited[j] && dist[j]<min){
min=dist[j];
u=j;
}
visited[u]=true;
if(min==inf) break;
for(int j=1;j<=n;j++){
double tmp=max(dist[u],map[u][j]);
if(!visited[j]&&dist[j]>tmp)
dist[j]=tmp;
}
}
} int main(){
//freopen("in.txt","r",stdin);
int cases=0,n;
while(scanf("%d",&n)!=EOF && n){
cases++;
for(int i=1;i<=n;i++)
scanf("%lf %lf",&nodes[i].x,&nodes[i].y);
init(n);
dijkstra(1,n);
printf("Scenario #%d\n",cases);
printf("Frog Distance = %.3lf\n\n",dist[2]);
}
}