#include
<
iostream
>
#include
<
algorithm
>
#include
<
limits
>
int
n,m;
int
graph[
1001
][
1001
];
bool
visite[
1001
];
int
result[
1001
];
![](/Images/OutliningIndicators/None.gif)
void
shortpath()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
memset( visite,
false
,
sizeof
(visite) );
memset( result,
0
,
sizeof
(result) );
![](/Images/OutliningIndicators/InBlock.gif)
visite[
1
]
=
true
;
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
1
; i
<=
n;
++
i )
result[i]
=
graph[
1
][i];
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
1
; i
<
n;
++
i )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
max
=
0
;
int
k
=
-
1
;
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
j
=
1
; j
<=
n;
++
j )
if
(
!
visite[j]
&&
result[j]
>
max )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
max
=
result[j];
k
=
j;
}
visite[k]
=
true
;
for
(
int
j
=
1
; j
<=
n;
++
j )
if
(
!
visite[j]
&&
graph[k][j]
>
0
&&
result[j]
<
std::min( result[k], graph[k][j] ) )
result[j]
=
std::min ( result[k], graph[k][j]);
}
}
int
main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
test;
scanf(
"
%d
"
,
&
test);
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
t
=
1
; t
<=
test;
++
t )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf(
"
%d%d
"
,
&
n,
&
m);
memset( graph,
0
,
sizeof
(graph) );
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
0
; i
<
m;
++
i )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
x, y,d;
scanf(
"
%d%d%d
"
,
&
x,
&
y,
&
d);
![](/Images/OutliningIndicators/InBlock.gif)
graph[x][y]
=
d;
graph[y][x]
=
d;
}
shortpath();
printf(
"
Scenario #%d:\n
"
, t );
printf(
"
%d\n
"
, result[n] );
printf(
"
\n
"
);
}
return
0
;
}
posted on 2008-10-02 17:39
Darren 阅读(256)
评论(0) 编辑 收藏 引用 所属分类:
图论