首页 > 代码库 > POJ - 2253 Frogger(最短路Dijkstra or flod)

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)