B - Frogger POJ - 2253————最短路变形

素颜马尾好姑娘i 2023-08-17 16:31 111阅读 0赞

[题目链接->][-]  
题意是：一个青蛙 到另一个青蛙的最短距离就是 最小必要跳跃的距离。  
其实这个题是单元最短路题变形体， 但是我为了简单 用了floyed， 这个时间也能过 ， 明天补题解

#include <cstdio>
    #include<iostream>
    #include<cmath>
    using namespace std;
    const double inf = 1e7;
    double mp[250][250];
    struct node { 
        double x, y;
    
    }marx[250];
    int n;
    void init()
    { 
        for(int i = 0;i <n;i++)
        { 
            for(int j = 0;j < n;j++)
            { 
                mp[i][j] = inf;
            }
        }
    
        for(int i = 0;i < n;i++)
        { 
            for(int j = 0;j < n;j++)
               		mp[j][i] = mp[i][j] = sqrt(pow(marx[i].x - marx[j].x, 2.0)+pow(marx[i].y - marx[j].y, 2.0));
        }
    
    }
    int main()
    { 
        int cnt = 0;
        while(cin >>n &&n!= 0)
        { 
            for(int i = 0;i <n;i++)
            { 
                cin>>marx[i].x>>marx[i].y;
            }
            init();
    
            for(int k = 0;k < n;k++)
            { 
                for(int i = 0;i < n;i++)
                { 
                    for(int j = 0;j < n;j++)
                    { 
                        if(mp[i][k]!= inf && mp[k][j]!=inf )
                        { 
    
                            mp[i][j] = min(mp[i][j], max(mp[i][k], mp[k][j]));
                        }
                    }
                }
            }
            printf("Scenario #%d\n", ++cnt);
            printf("Frog Distance = %.3f\n\n", mp[0][1]);
        }
        return 0;
    }

[-]: https://vjudge.net/contest/313997#problem/B

发表评论取消回复

表情：

评论列表（有 0 条评论，111人围观）

还没有评论，来说两句吧...

相关阅读

相关最短路径？青蛙(Frogger), ZOJ1942, POJ2253

感觉只是用了最短路径的思想啊。 bellman算法是神奇的迭代，dijkstra是神奇的贪心。看了下面这个图，感到这特么就是个最小生成树的计算过程啊。 ![Center

朴灿烈づ我的快乐病毒、/ 2024年02月17日 23:47/ 0 赞/ 49 阅读

相关 B - Frogger POJ - 2253————最短路变形

[题目链接->][-] 题意是：一个青蛙到另一个青蛙的最短距离就是最小必要跳跃的距离。其实这个题是单元最短路题变形体，但是我为了简单用了floyed，这个时

素颜马尾好姑娘i/ 2023年08月17日 16:31/ 0 赞/ 112 阅读

相关 [kuangbin带你飞]专题四最短路练习 B（ POJ 2253） Frogger（spfa）

B - Frogger（spfa）题目链接：[https://vjudge.net/contest/66569\problem/B][https_vjudge.net_

- 日理万妓/ 2023年08月17日 15:40/ 0 赞/ 123 阅读

相关最短路poj 1125

题目：[poj1125Stockbroker Grapevine][poj1125_Stockbroker Grapevine] 题意：此题题意远比题目难

刺骨的言语ヽ痛彻心扉/ 2022年08月27日 15:54/ 0 赞/ 167 阅读

相关 POJ 2253-Frogger（最小生成树-给定终点）

Frogger <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

柔情只为你懂/ 2022年07月11日 12:25/ 0 赞/ 135 阅读

相关 POJ2253 Frogger(Floyd)

题目描述：青蛙A要找青蛙B，路径任选，求所有可能路径中跳的最远的一步，它们之中的最小距离值。输入要求，第一行为石头数，二三行为起点和终点位置，n-2行为其他石头结点。第一

╰半橙微兮°/ 2022年07月11日 06:56/ 0 赞/ 119 阅读

相关 POJ 2253 Frogger floyd变形

滴，集训第二十五天打卡。最近又好热好热了呀... POJ 2253 Frogger Freddy Frog is sitting on a stone in the m

曾经终败给现在/ 2022年06月10日 05:55/ 0 赞/ 159 阅读

相关 poj-2253-Frogger

Frogger <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

ゝ一世哀愁。/ 2022年05月28日 12:07/ 0 赞/ 129 阅读

相关 POJ - 2253 Frogger(迪杰斯特拉变形)

Frogger Description Freddy Frog is

素颜马尾好姑娘i/ 2022年05月19日 14:29/ 0 赞/ 146 阅读