美文网首页
poj -2253 Frogger 最短路算法之dijkstra

poj -2253 Frogger 最短路算法之dijkstra

作者: Anxdada | 来源:发表于2017-03-18 20:03 被阅读0次

    题意:第一个点是青蛙的坐标,第二个是青蛙妹子的坐标,其他的点是石头的坐标,现在要问青蛙到青蛙妹子的地方,至少需要跳的最大距离,不是最短路问题,路可以很长,跳的石头很多,要求是跳的最大距离,最小(理解好!!!)

    代码如下:(这是最短路的做法)

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #define ll long long
    #define db double
    using namespace std;
    #define INF 99999999
    const int maxn=205;
    db maze[maxn][maxn],low[maxn],sh;
    int ca[maxn][2],vis[maxn];
    int n;
    
    void dijkstra()
    {
        for(int i=0;i<n;i++){
            low[i]=maze[0][i];
            vis[i]=1;
        }
        vis[0]=0;
    
        int u=-1;
        for(int i=1;i<n;i++)
        {   int minn=999999;
            for(int j=0;j<n;j++)
            {
                if(vis[j] && minn>low[j]){
                    minn=low[j],u=j;
                }
            }
            vis[u]=0;
            for(int j=0;j<n;j++)
            {
                low[j]=min(max(low[u],maze[u][j]),low[j]);
            }
        }
        sh=low[1];
        for(int j=0;j<n;j++){
            printf("%.2f\n",low[j]);
        }
    }
    int main()
    {   int ans=1;
        while(~scanf("%d",&n) && n)
        {
            memset(maze,0,sizeof(maze));
            memset(ca,0,sizeof(ca));
            for(int i=0;i<n;i++)
            {
                scanf("%d %d",&ca[i][0],&ca[i][1]);
            }
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    maze[i][j]=sqrt(1.0*(ca[i][0]-ca[j][0])*(ca[i][0]-ca[j][0])+1.0*(ca[i][1]-ca[j][1])*(ca[i][1]-ca[j][1]));
                }
                maze[i][i]=0.0;
            }
            /*for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                   printf("%.3f ",maze[i][j]);
                }
                printf("\n");
            }*/
            dijkstra();
            printf("Scenario #%d\nFrog Distance = %.3f\n\n",ans++,sh);
        }
    }
    
    

    还可以用最小生成树做,这种方法异常巧妙.把所有的点的距离都算出来然后根据距离的长短排个序,从小到大的一次连接起来,每连一次就判断下青蛙是否和妹子相遇,如相遇则输出连的那个长度.哇,这种方法才是最好的.

    代码如下:

    //哇,这个方法才是真的又好敲,又好巧.!
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #define CLR(x) memset(x,0,sizeof(x))
    #define ll long long int
    #define db double
    using namespace std;
    const int maxn=205;
    int pre[maxn];
    db cal[maxn][2];
    int cas=1;
    struct point
    {
        int x,y;
        db dis;
    }s[maxn*maxn];
    
    void init()
    {
        for(int i=0;i<maxn;i++)
            pre[i]=i;
    
    }
    
    int Find(int x)
    {
        return pre[x]==x?x:pre[x]=Find(pre[x]);
    }
    
    void un(int x,int y)
    {
        int m=Find(x);
        int n=Find(y);
        if(m!=n)
            pre[n]=m;
    }
    
    bool cmp(point a,point b)
    {
        return a.dis<b.dis;
    }
    
    int main()
    {
        int n;
        while(~scanf("%d",&n) && n){
            init();
            for(int i=0;i<n;i++){
                scanf("%lf %lf",&cal[i][0],&cal[i][1]);
            }
            int cnt=0;
            for(int i=0;i<n;i++){
                for(int j=i+1;j<n;j++){
                    s[cnt].x=i;
                    s[cnt].y=j;
                    s[cnt].dis=sqrt(fabs(pow(cal[i][0]-cal[j][0],2)+pow(cal[i][1]-cal[j][1],2)));
                    cnt++;
                }
            }
            sort(s,s+cnt,cmp);
            db m;
            for(int i=0;i<cnt;i++){
                m=s[i].dis;
                un(s[i].x,s[i].y);
                if(Find(pre[0])==Find(pre[1]))
                    break;
            }
            printf("Scenario #%d\n",cas++);
            printf("Frog Distance = %.3f\n\n",m);
        }
    }
    
    

    相关文章

      网友评论

          本文标题:poj -2253 Frogger 最短路算法之dijkstra

          本文链接:https://www.haomeiwen.com/subject/awhpnttx.html