#include
<
iostream
>
#include
<
cmath
>
#include
<
limits
>
struct
Point
{
int
x,y;
}
;
double
graph[
201
][
201
];
Point data[
201
];
int
n;
bool
visite[
201
];
double
result[
201
];
double
Distance( Point
&
a, Point
&
b )
{
return
sqrt( (
double
)( (a.x
-
b.x)
*
(a.x
-
b.x )
+
(a.y
-
b.y )
*
(a.y
-
b.y ) ) );
}
void
shortpath(
int
t )
{
for
(
int
i
=
1
; i
<=
n;
++
i )
{
visite[i]
=
false
;
result[i]
=
0.0
;
}
for
(
int
i
=
1
; i
<=
n;
++
i )
result[i]
=
graph[t][i];
visite[t]
=
true
;
for
(
int
i
=
1
; i
<=
n
-
1
;
++
i )
{
double
min
=
std::numeric_limits
<
double
>
::max();
int
k
=
-
1
;
for
(
int
j
=
1
; j
<=
n;
++
j )
if
(
!
visite[j]
&&
result[j]
<
min )
{
min
=
result[j];
k
=
j;
}
visite[k]
=
true
;
for
(
int
j
=
1
; j
<=
n;
++
j )
if
(
!
visite[j]
&&
std::max( graph[k][j], result[k] )
<
result[j] )
result[j]
=
std::max( graph[k][j], result[k] );
}
}
int
main()
{
int
num
=
1
;
while
( scanf(
"
%d
"
,
&
n), n
!=
0
)
{
for
(
int
i
=
1
; i
<=
n;
++
i )
scanf(
"
%d%d
"
,
&
data[i].x,
&
data[i].y );
for
(
int
i
=
1
; i
<=
n;
++
i )
for
(
int
j
=
1
; j
<=
n;
++
j )
graph[i][j]
=
Distance( data[i], data[j] );
shortpath(
1
);
printf(
"
Scenario #%d\n
"
, num
++
);
printf(
"
Frog Distance = %.3lf\n
"
, result[
2
] );
printf(
"
\n
"
);
}
return
0
;
}
posted on 2008-10-02 15:24
Darren 阅读(236)
评论(0) 编辑 收藏 引用 所属分类:
图论