POJ-2253 Flogger(最短絡)(Floyedアルゴリズム)(コメント詳細)
POJ-2253 Froger (Flooyedアルゴリズム)
Problem
Fredy Froog is sitting on a stone in the middle of a lake.Suddenly he notices Fiona Froog who is sitting on another stone.He plans to visit her,but since the water is dirty and full of tourists'sunscreen Unfortunaly Fiona's stone is out of his jump range.The refore Fredy considers to use other stones as intermediate stops and reach her by a sequence of several small jump. To execute a given sequence of jmps,a froog's jump range oviouslymust be at leas long as the longest jump occuring in the sequence. The frog distance(huomans also call it minimex distance)between two stones therefore is defined as the minimum necessary jum over all possible Paths between the twostones.s. You are given the coordinance of Fredy's stone、Fiona's stone、all other stones in the lake.Your job is to coput the flogdistance between Fredy's and Fiona's stone.
Input
The input will contain one or more test case s.The first line of each test case will contain the number of stones n(=n==200).The next n line each contain two integers xi(0==xi,yStore==1000 Presentone).The.the other n-2 stones are unoccupied.The e's a blank line follwing each test case.Input is terminated by a value ofゼロ(0)for n.
Output
For each test case,print a line saying“Scienaro”and a line sayng“Frog Distance=y”where x is replacced by the test case number(they are numbend from 1)and y is replace bythe proprinese inese.place.Prinest inest.
Sample Input
件名:
湖の中にはnつの石があります.番号は1からnまでで、2匹のカエルがいます.ボブは1号の石の上で、Aliceは2号の石の上で、ボブはAliceを見舞いに行きたいです.しかし、アリスの石は彼のジャンプの範囲を超えています.そのため、ボブは他の石を使って中間駅として、一連の小さなジャンプを通じて彼女に到着しました.二つの石の間の蛙の距離は二つの石の間のあらゆる可能な経路における最小必要なジャンプ距離と定義されています.ある経路の必要なジャンプ距離、つまりこの経路の中で一回のジャンプの一番遠いジャンプ距離です.(すべてのパスの中で一番長い端を求めて、これらの一番長い端の中で最小値を見つけて出力します.)
複数の例の入力は、まず1つの整数nを入力して石の数を表し、nが0に等しい場合に終了します.次に2+1行ずつ、1からnまでの石の座標xi,yiを与えます.
まず「Scienaro嗳x」を出力し、xはサンプル番号を表します.次の行は「Frog Distance=y」を出力します.yはあなたが得た答えを表します.サンプルごとに空行を出力します.
考え方:
今はすべての通路の最大距離を求めて、これらの最大距離を比較して、一番小さいのをカエルの最小距離とします.
＜div id=「right-1」class=「col-lg-12 col-sm-4 col-xs-4 ad」
＜div id=「right-2」class=「col-lg-12 col-sm-4 col-xs-4 ad」
＜div id=「right-3」class=「col-lg-12 col-sm-4 col-xs-4 ad」
Problem
Fredy Froog is sitting on a stone in the middle of a lake.Suddenly he notices Fiona Froog who is sitting on another stone.He plans to visit her,but since the water is dirty and full of tourists'sunscreen Unfortunaly Fiona's stone is out of his jump range.The refore Fredy considers to use other stones as intermediate stops and reach her by a sequence of several small jump. To execute a given sequence of jmps,a froog's jump range oviouslymust be at leas long as the longest jump occuring in the sequence. The frog distance(huomans also call it minimex distance)between two stones therefore is defined as the minimum necessary jum over all possible Paths between the twostones.s. You are given the coordinance of Fredy's stone、Fiona's stone、all other stones in the lake.Your job is to coput the flogdistance between Fredy's and Fiona's stone.
Input
The input will contain one or more test case s.The first line of each test case will contain the number of stones n(=n==200).The next n line each contain two integers xi(0==xi,yStore==1000 Presentone).The.the other n-2 stones are unoccupied.The e's a blank line follwing each test case.Input is terminated by a value ofゼロ(0)for n.
Output
For each test case,print a line saying“Scienaro”and a line sayng“Frog Distance=y”where x is replacced by the test case number(they are numbend from 1)and y is replace bythe proprinese inese.place.Prinest inest.
Sample Input
2
0 0
3 4
3
17 4
19 4
18 5
0
Scenario #1
Frog Distance = 5.000
Scenario #2
Frog Distance = 1.414件名:
湖の中にはnつの石があります.番号は1からnまでで、2匹のカエルがいます.ボブは1号の石の上で、Aliceは2号の石の上で、ボブはAliceを見舞いに行きたいです.しかし、アリスの石は彼のジャンプの範囲を超えています.そのため、ボブは他の石を使って中間駅として、一連の小さなジャンプを通じて彼女に到着しました.二つの石の間の蛙の距離は二つの石の間のあらゆる可能な経路における最小必要なジャンプ距離と定義されています.ある経路の必要なジャンプ距離、つまりこの経路の中で一回のジャンプの一番遠いジャンプ距離です.(すべてのパスの中で一番長い端を求めて、これらの一番長い端の中で最小値を見つけて出力します.)
複数の例の入力は、まず1つの整数nを入力して石の数を表し、nが0に等しい場合に終了します.次に2+1行ずつ、1からnまでの石の座標xi,yiを与えます.
まず「Scienaro嗳x」を出力し、xはサンプル番号を表します.次の行は「Frog Distance=y」を出力します.yはあなたが得た答えを表します.サンプルごとに空行を出力します.
考え方:
今はすべての通路の最大距離を求めて、これらの最大距離を比較して、一番小さいのをカエルの最小距離とします.
#include
#include
#include
#include
#include
#define maxn 300
#define INF 0x3f3f3f3f
using namespace std;
int x[maxn],y[maxn],n;
double mapp[maxn][maxn];
void floyd()
{
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
mapp[i][j]=min(mapp[i][j],max(mapp[i][k],mapp[k][j]));//
//i->k,k->j i->j ，
// i->k,k->j i->j ， i->k->j ， i->j
}
int main()
{
int q=1;
while(cin>>n&&n)
{
for(int i=0; i<=n; i++)
{
for(int j=0; j<=0; j++)
{
if(i==j)
mapp[i][j]=0;
else
mapp[i][j]=INF;
}
}
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++)//
mapp[i][j]=mapp[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
Frog Distance = %.3f
",q++,mapp[1][2]);
/*cout< ＜div id=「right-1」class=「col-lg-12 col-sm-4 col-xs-4 ad」
＜div id=「right-2」class=「col-lg-12 col-sm-4 col-xs-4 ad」
＜div id=「right-3」class=「col-lg-12 col-sm-4 col-xs-4 ad」