水題,但是g++超時,c++對了 不解
#include<stdio.h>
const
int
MAXN=
505
;
const
int
INF=
0x7fffffff
;
int
xx[MAXN];
int
pre[MAXN];
int
map[MAXN][MAXN];
int
dist[MAXN];
int
ans,n,flag;
void
Prim()
{
int
i,j,k;
int
mn;
bool
p[MAXN];
for
(i=
2
;i<=n;i++
)
{
p[i]
=
false
;
pre[i]
=
1
;
dist[i]
=map[
1
][i];
}
dist[
1
]=
0
;
p[
1
]=
true
;
for
(i=
1
;i<=n-
1
;i++
)
{
mn
=
INF;
k
=
0
;
for
(j=
1
;j<=n;j++
)
{
if
(!p[j] && dist[j]<
mn)
{
mn
=
dist[j];
k
=
j;
}
}
if
(k==
0
) {flag=
1
;
return
;}
p[k]
=
true
;
ans
+=
dist[k];
for
(j=
1
;j<=n;j++
)
{
if
(!p[j] && map[k][j]!=INF && dist[j]>
map[k][j])
{
dist[j]
=
map[k][j];
pre[j]
=
k;
}
}
}
}
int
main()
{
int
T;
int
m,k,t,i,j,a,b,c;
int
xx[MAXN];
scanf(
"
%d
"
,&
T);
while
(T--
)
{
scanf(
"
%d%d%d
"
,&n,&m,&
k);
{
for
(i=
1
;i<=n;i++
)
{
for
(j=
1
;j<=n;j++
)
{
if
(i==j) map[i][j]=
0
;
else
map[i][j]=
INF;
}
}
for
(i=
0
;i<m;i++
)
{
scanf(
"
%d%d%d
"
,&a,&b,&
c);
if
(map[a][b]>c) map[a][b]=map[b][a]=
c;
}
for
(i=
0
;i<k;i++
)
{
scanf(
"
%d
"
,&
t);
for
(j=
0
;j<t;j++
)
scanf(
"
%d
"
,&
xx[j]);
for
(j=
1
;j<t;j++
)
{
map[xx[j]][xx[j
-
1
]]=map[xx[j-
1
]][xx[j]]=
0
;
}
}
ans
=flag=
0
;
Prim();
if
(flag) printf(
"
-1\n
"
);
else
printf(
"
%d\n
"
,ans);
}
}
return
0
;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061
微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元

