#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 閱讀(242)
評論(0) 編輯 收藏 引用 所屬分類:
圖論