B - Frogger（spfa）

題目鏈接：https://vjudge.net/contest/66569#problem/B

題目：

Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists' sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona's stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog's jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.

You are given the coordinates of Freddy's stone, Fiona's stone and all other stones in the lake. Your job is to compute the frog distance between Freddy's and Fiona's stone.
Input The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy's stone, stone #2 is Fiona's stone, the other n-2 stones are unoccupied. There's a blank line following each test case. Input is terminated by a value of zero (0) for n. Output For each test case, print a line saying "Scenario #x" and a line saying "Frog Distance = y" where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one. Sample Input 2 0 0 3 43 17 4 19 4 18 50 Sample Output Scenario #1 Frog Distance = 5.000Scenario #2 Frog Distance = 1.414
題意：有兩只青蛙和若干塊石頭，現(xiàn)在已知這些東西的坐標(biāo)，兩只青蛙A坐標(biāo)和青蛙B坐標(biāo)是第一個(gè)和第二個(gè)坐標(biāo)，
現(xiàn)在A青蛙想要到B青蛙那里去，并且A青蛙可以借助任意石頭的跳躍，而從A到B有若干通路，
問從A到B的所有通路上的最大邊，比如有? 有兩條通路? 1(4)5 (3）2 代表1到5之間的邊為4,? 5到2之間的邊為3，那么該條通路跳躍范圍（兩塊石頭之間的最大距離）為 4，?
另一條通路 1(6) 4(1) 2 ，該條通路的跳躍范圍為6， 兩條通路的跳躍范圍分別是 4 ，6，我們要求的就是最小的那一個(gè)跳躍范圍，即4,用三種方法都能解決
思路：最短路模板題，稍微變化一下，就是每條路徑選取最大的，選取這幾條路徑中最小的，即把模板中d[i]>d[now]+lu[now][i]改成d[i]>max(d[now],lu[now][i])就行了，
WA了很多遍由于初始化的原因，spfa算法代碼如下：


// // Created by hanyu on 2019/7/14. // #include<iostream> #include<algorithm> #include<queue> #include<map> #include<cstring> #include<cstdio> #include<math.h> using namespace std; typedef long long ll; #define MAX 0x3f3f3f3f const int maxn=1005; double d[maxn]; double lu[maxn][maxn]; bool book[maxn]; int n; void spfa(int a) {for(int i=2;i<=n;i++){d[i]=MAX;book[i]=false;}//memset(book,false,sizeof(book))//memset(d,MAX,sizeof(d))//還是別用以上注釋用的memset初始化，就因?yàn)檫@個(gè)WA了很多遍，找了兩個(gè)小時(shí)的錯(cuò)誤,不曉得為啥queue<int>qu;d[a]=false;book[a]=true;qu.push(a);int now;while(!qu.empty()){now=qu.front();qu.pop();book[now]=false;for(int i=1;i<=n;i++){if(d[i]>max(d[now],lu[now][i])){d[i]=max(d[now],lu[now][i]);if(!book[i]){qu.push(i);book[i]=true;}}}} } int main() {int k=0;int a[maxn],b[maxn];while(~scanf("%d",&n)) {if (n == 0)break;for (int i = 1; i <= n; i++) {scanf("%d%d", &a[i], &b[i]);}for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++) {lu[i][j] = lu[j][i] = sqrt(double(a[i] - a[j]) * (a[i] - a[j]) +double(b[i] - b[j]) * (b[i] - b[j]));}}spfa(1);k++;printf("Scenario #%d\n",k);printf("Frog Distance = %.3lf\n\n",d[2]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Vampire6/p/11202573.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的[kuangbin带你飞]专题四 最短路练习 B（ POJ 2253） Frogger（spfa）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。