POJ-2253(最短路变形+dijikstra算法+求解所有路径中所有最长边中的一个最小值)

frogger

POJ-2253

  • 这题的代码特别像prim求解最小生成树的代码,其实两者本来也很像。
  • 这里的d数组不再维护的起点到该点的最短距离了,而是路径中的最长距离。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
const double INF=0X3F3F3F3F;
const int maxn=201;
int n;
double map[maxn][maxn];
int x[maxn];int y[maxn];
double d[maxn];
bool vis[maxn];
void dijikstra(int s){
    for(int i=1;i<=n;i++){
        d[i]=map[1][i];
    }
    for(int i=1;i<=n;i++){
        int v=-1;
        double mins=INF;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&mins>d[j]){//
                v=j;
                mins=d[j];
            }
        }
        if(v==-1)
            break;
        vis[v]=1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&d[j]>max(d[v],map[v][j])){
                d[j]=max(d[v],map[v][j]);
            }
        }
    }
}
int main(){
    int k=0;
    while(cin>>n&&n){
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            cin>>x[i]>>y[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                map[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            }
        }
        dijikstra(1);
        cout<<"Scenario #"<<++k<<endl;
        printf("Frog Distance = %.3f\n\n",d[2]);
    }
    return 0;
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。