#include
<
iostream
>
using
namespace
std;
int
N,M;
int
g[
110
][
110
];
int
d[
110
][
110
];
int
m[
110
][
110
];
int
c
=
0
,ans[
110
];
void
dfs(
int
x,
int
y){
if
(m[x][y]
==-
1
)
return
;
dfs(x,m[x][y]);
ans[
++
c]
=
m[x][y];
dfs(m[x][y],y);
}
int
main()
{
while
(
1
){
scanf(
"
%d
"
,
&
N);
if
(N
==-
1
)
break
;
scanf(
"
%d
"
,
&
M);
for
(
int
i
=
1
;i
<=
N;
++
i)
for
(
int
j
=
1
;j
<=
N;
++
j)
g[i][j]
=
0xFFFFFFF
;
int
x,y,z;
for
(
int
i
=
1
;i
<=
M;
++
i){
scanf(
"
%d%d%d
"
,
&
x,
&
y,
&
z);
if
(g[x][y]
>
z)
g[x][y]
=
g[y][x]
=
z;
}
for
(
int
i
=
1
;i
<=
N;
++
i)
for
(
int
j
=
1
;j
<=
N;
++
j)
d[i][j]
=
g[i][j];
memset(m,
-
1
,
sizeof
(m));
int
Min
=
10000000
;
for
(
int
k
=
1
;k
<=
N;
++
k){
for
(
int
i
=
1
;i
<
k;
++
i)
for
(
int
j
=
i
+
1
;j
<
k;
++
j)
if
(d[i][k]
+
d[k][j]
+
g[i][j]
<
Min){
Min
=
d[i][k]
+
d[k][j]
+
g[i][j];
c
=
2
;
ans[
1
]
=
k;
ans[c]
=
i;
dfs(i,j);
ans[
++
c]
=
j;
}
for
(
int
i
=
1
;i
<=
N;
++
i)
for
(
int
j
=
i
+
1
;j
<=
N;
++
j)
if
(g[i][j]
>
g[i][k]
+
g[k][j]){
g[i][j]
=
g[i][k]
+
g[k][j];
g[j][i]
=
g[i][j];
m[i][j]
=
m[j][i]
=
k;
}
}
if
(Min
==
10000000
) printf(
"
No solution.\n
"
);
else
{
for
(
int
i
=
1
;i
<
c;
++
i)
printf(
"
%d
"
,ans[i]);
printf(
"
%d\n
"
,ans[c]);
}
}
return
0
;
}
posted on 2009-05-29 16:35
xfstart07 阅读(214)
评论(0) 编辑 收藏 引用 所属分类:
代码库