POJ - 2253 Frogger（最短路Dijkstra or flod）

题意：要从起点的石头跳到终点的石头，设The frog distance为从起点到终点的某一路径中两点间距离的最大值，问在从起点到终点的所有路径中The frog distance的最小值为多少。

分析：

解法一:Dijkstra，修改最短路模板，d[u]表示从起点到u的所有路径中两点间距离的最大值的最小值。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-15;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 200 + 10;

const int MAXT = 10000 + 10;

using namespace std;

struct Edge{

    int from, to;

    double dist;

    Edge(int f, int t, double d):from(f), to(t), dist(d){}

};

struct HeapNode{

    double d;

    int u;

    HeapNode(double dd, int uu):d(dd), u(uu){}

    bool operator < (const HeapNode& rhs)const{

        return d > rhs.d;

    }

};

struct Dijkstra{

    int n, m;

    vector<Edge> edges;

    vector<int> G[MAXN];

    double d[MAXN];

    bool done[MAXN];

    void init(int n){

        this -> n = n;

        for(int i = 0; i <= n; ++i) G[i].clear();

        edges.clear();

    }

    void AddEdge(int from, int to, double dist){

        edges.push_back(Edge(from, to, dist));

        m = edges.size();

        G[from].push_back(m - 1);

    }

    void dijkstra(int s){

        priority_queue<HeapNode> Q;

        for(int i = 0; i <= n; ++i){

            d[i] = 10000000.0;

        }

        memset(done, false, sizeof done);

        d[s] = 0;

        Q.push(HeapNode(0, s));

        while(!Q.empty()){

            HeapNode x = Q.top();

            Q.pop();

            int u = x.u;

            if(done[u]) continue;

            done[u] = true;

            for(int i = 0; i < G[u].size(); ++i){

                Edge &e = edges[G[u][i]];

                double tmp = max(d[u], e.dist);

                if(tmp < d[e.to]) {

                    d[e.to] = tmp;

                    Q.push(HeapNode(d[e.to], e.to));

                }

            }

        }

    }

}dij;

struct Node{

    int x, y;

    void read(){

        scanf("%d%d", &x, &y);

    }

}num[MAXN];

double getD(Node& a, Node &b){

    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

}

int main(){

    int n;

    int kase = 0;

    while(scanf("%d", &n) == 1){

        if(!n) return 0;

        for(int i = 0; i < n; ++i) num[i].read();

        dij.init(n);

        for(int i = 0; i < n; ++i){

            for(int j = i + 1; j < n; ++j){

                double d = getD(num[i], num[j]);

                dij.AddEdge(i, j, d);

                dij.AddEdge(j, i, d);

            }

        }

        dij.dijkstra(0);

        printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++kase, dij.d[1]);

    }

    return 0;

}

解法二：flod，pic[i][j]表示从i到j的所有路径中两点间距离的最大值的最小值。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 200 + 10;

const int MAXT = 10000 + 10;

using namespace std;

double pic[MAXN][MAXN];

struct Node{

    int x, y;

    void read(){

        scanf("%d%d", &x, &y);

    }

}num[MAXN];

double getD(Node& a, Node &b){

    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));

}

int main(){

    int n;

    int kase = 0;

    while(scanf("%d", &n) == 1){

        if(!n) return 0;

        for(int i = 0; i < n; ++i) num[i].read();

        for(int i = 0; i < n; ++i){

            for(int j = i + 1; j < n; ++j){

                double d = getD(num[i], num[j]);

                pic[i][j] = pic[j][i] = d;

            }

        }

        for(int k = 0; k < n; ++k){

            for(int i = 0; i < n; ++i){

                for(int j = i + 1; j < n; ++j){

                    if(pic[i][k] < pic[i][j] && pic[k][j] < pic[i][j]){

                        pic[j][i] = pic[i][j] = max(pic[i][k], pic[k][j]);

                    }

                }

            }

        }

        printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++kase, pic[0][1]);

    }

    return 0;

}

巴特西

POJ - 2253 Frogger（最短路Dijkstra or flod）

最新文章

热门文章