您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ 2253 Frogger

卞振伟2019-07-25【ACM||算法】人已围观

简介B POJ 2253 Frogger


题意:
有一只青蛙要从A点跳到B点。青蛙由于身体机能限制,所以有一个极限跳跃远度。
求:这个极限最少是多少,才能完成这个任务。点是二维坐标,其中第一个点是A点,第二个点是B点。
思路:
最小最大路,整体最小局部(每条路)最大,所有路中最大的————每个路中最小的。
if( d[j] > max(d[k], G[k][j]) )
d[j] = max(d[k], G[k][j]);

dijkstra

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int n;
int x[maxn], y[maxn];
double G[maxn][maxn];
double d[maxn];
int vst[maxn];

void Dijkstra(int s){
    for(int i = 0; i <= n; ++i){
        vst[i] = 0;
        d[i] = inf;
    } 
    vst[s] = 1;
    d[s] = 0;
    for(int i = 0; i < n-1; ++i){
        int Min = inf;
        int k = s;
        for(int j = 0; j < n; ++j){
            if(!vst[j] &&  Min > d[j]){
                Min = d[j];
                k = j;
            }
        }
        vst[k] = 1;
        for(int j = 0; j < n; ++j){
            if(G[k][j])
                d[j] = min(d[j],  max(d[k], G[k][j]) );
        }
    }
}

int main(){
    int cot = 1;
    while(~scanf("%d",&n) && n){
        memset(G,0,sizeof(G));
        for(int i = 0; i < n; ++i){
            scanf("%d%d",&x[i],&y[i]);
        }
        for(int i = 0; i < n; ++i){
            for(int j = i+1; j < n; ++j){
                G[i][j] = G[j][i] = sqrt( (double)(x[i]-x[j]) * (double)(x[i]-x[j]) + 
                                          (double)(y[i]-y[j]) * (double)(y[i]-y[j]) );
            }
        }
        Dijkstra(0);
        printf("Scenario #%d\nFrog Distance = %.3lf\n\n",cot++,d[1]);
    }

    return 0;
}

floyd

#include<cstdio>
#include<string.h>
#include<cmath>
#include<algorithm>

using namespace std;

const int maxn = 1010;

double G[maxn][maxn];
int x[maxn];
int y[maxn];
int n;
void Floyd(){
    for(int k = 0; k < n; ++k){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                G[i][j] = min(G[i][j], max(G[i][k], G[k][j]));
            }
        }
    }
}

int main(){
    int cot = 1;
    while(~scanf("%d", &n) && n){
        memset(G, 0, sizeof(G));
        for(int i = 0; i < n; ++i){
            scanf("%d%d", &x[i], &y[i]);
        }
        for(int i = 0; i < n; ++i){
            for(int j = i+1; j < n; ++j){
                G[i][j] = G[j][i] = sqrt((double)(x[i]-x[j]) * (double)(x[i]-x[j]) + (double)(y[i]-y[j]) * (double)(y[i]-y[j]) );
            }
        }
        Floyd();
        printf("Scenario #%d\nFrog Distance = %.3lf\n\n", cot++, G[0][1]);
    }
    return 0;
}

spfa

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;

int n;
int x[maxn], y[maxn];
double G[maxn][maxn];
int vst[maxn];
double d[maxn];

void spfa(int s){
   queue<int> q;
   q.push(s);
   for(int i = 0; i < n; ++i){
       vst[i] = 0;
       d[i] = inf;
   }
   vst[s] = 1;
   d[s] = 0;
   while(!q.empty()){
        int k = q.front();
        q.pop();
        vst[k] = 0;
        for(int j = 0; j < n; ++j){
            if( d[j] > max(d[k], G[k][j]) ){
                d[j] = max(d[k], G[k][j]);
                if(vst[j] == 0){
                    vst[j] = 1;
                    q.push(j);
                }
            }
        }
   }
}

int main(){
    int cot = 1;
    while(~scanf("%d",&n) && n){
        memset(G,0,sizeof(G));
        for(int i = 0; i < n; ++i){
            scanf("%d%d",&x[i],&y[i]);
        }
        for(int i = 0; i < n; ++i){
            for(int j = i+1; j < n; ++j){
                G[i][j] = G[j][i] = sqrt( (double)(x[i]-x[j]) * (double)(x[i]-x[j]) +
                                          (double)(y[i]-y[j]) * (double)(y[i]-y[j]) );
            }
        }
        spfa(0);
        printf("Scenario #%d\nFrog Distance = %.3lf\n\n",cot++,d[1]);
    }

    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00