Frogger Detailed Problem Solution POJ2253

Frogger Problem Solution POJ2253

There are N stones, coordinates are (xi, yi), the frog is in position 1, the end point is in position 2, there are M edges, the frog may have one or many paths to reach the end point, find out the minimum of the maximum edge weight in these paths.

Analysis: We often use a d[x] array to record the shortest path to the current position x when solving the shortest path, then the final d[n] is our total shortest path.
The same is true for this problem. We use d[x] to record the minimum and maximum edge weights of x up to the current position.
MAX = max (d [u], MAPP [u] [x]), D [i] = min (d [i], MAX);
So the last d is our answer. Both dijkstra and SPFA can be used to solve the problem.

Note:
1. Since the title only tells the coordinates of the points, it is necessary to run an n^2 to compute the adjacency matrix table mapp[i][j]
2. Because of sqrt, float or double are used for data types.
3. I don't know why poj can't pass G++ or C++.

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<queue>
#define ll long long
#define pb push_back
using namespace std;
const int maxn=250;
const int INF=1e9;
bool vis[maxn];

struct node
{
double x,y;
} p[maxn];
double mapp[maxn][maxn];
double d[maxn];
double dis(double x1,double y1,double x2,double y2)
{
double xx=x1-x2;
double yy=y1-y2;
return sqrt(xx*xx+yy*yy);
}
int n,K=0;
inline float SPFA(int sx,int ex)
{
memset(vis,false,sizeof vis);
for (int i=1; i<=n; i++)
d[i]=INF;
queue<int> q;
vis[sx]=true;
q.push(sx);
d[sx]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=false;
for (int i=1; i<=n; i++)
{
if (i!=u)
{
double ans=max(d[u],mapp[u][i]);//Comparing the maximum edge weight d[u] on 1-u with the edge weight u to i, taking max is the updated d[i]
if (ans<d[i])//If it's smaller than the current maximum edge weight, it fits the question and changes it.
{
d[i]=ans;
if (!vis[i])
{
vis[i]=true;
q.push(i);
}
}
}
}
}
return d[ex];
}
int main()
{
while(~scanf("%d",&n)&&n)
{
for (int i=1; i<=n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
mapp[i][j]=INF;
}
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
mapp[i][j]=dis(p[i].x,p[i].y,p[j].x,p[j].y);
}
}
printf("Scenario #%d\n",++K);
printf("Frog Distance = %.3lf\n\n",SPFA(1,2));
}
return 0;
}

Posted on Sat, 12 Oct 2019 09:32:49 -0700 by Jeller