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[2] 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