#include
<
iostream
>
#include
<
stdio.h
>
#include
<
cstring
>
using
namespace
std;
#define
INF 5000000
int
a[
201
];
int
c[
201
][
201
];
int
d[
201
][
201
];
int
main(){
int
n;
int
i,j,m,kk,k,p;
int
max1; scanf(
"
%d
"
,
&
n);
int
l;
for
(l
=
1
;l
<=
n;l
++
) { memset(a,
0
,
sizeof
(a)); memset(c,
0
,
sizeof
(c)); memset(d,
0
,
sizeof
(d)); scanf(
"
%d
"
,
&
m);
for
( i
=
0
;i
<
m;i
++
) scanf(
"
%d
"
,
&
a[i]);
for
(i
=
0
;i
<
m;i
++
)
for
(j
=
0
;j
<
m;j
++
) { scanf(
"
%d
"
,
&
d[i][j]);
if
(d[i][j]
==-
1
) d[i][j]
=
INF; } max1
=
0
;
for
(k
=
0
;k
<
m;k
++
)
for
(i
=
0
;i
<
m;i
++
)
for
(j
=
0
;j
<
m;j
++
) {
if
(d[i][j]
>
(d[i][k]
+
d[k][j])) d[i][j]
=
d[i][k]
+
d[k][j]; } kk
=
0
;
for
(p
=
0
;p
<
m;p
++
) {
if
(p
<
m
-
1
) { max1
+=
d[a[p]][a[p
+
1
]];
if
(d[a[p]][a[p
+
1
]]
==
INF) kk
=
1
; }
else
{ max1
+=
d[a[p]][a[
0
]];
if
(d[a[p]][a[
0
]]
==
INF) {kk
=
1
;} } }
if
(kk
==
1
) printf(
"
impossible\n
"
);
else
printf(
"
%d\n
"
,max1); }
return
0
;}
转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048253.html
相关资源：JAVA上百实例源码以及开源项目
