3073. Country Road 一道经典最小生成树问题，我是用C++写的，请大家帮忙看看。
我的代码一直是WA（C++），请大家帮忙看看。
网址：http://acm.tju.edu.cn/toj/showp3073.html
大概题意：输入：每组测试数据都包含n,m,k;n:1到n为编号，m行为已经连接的。k行为连接的两点，及两点间距离。
输出：把所以点都连上的最短路，不能都连上输出-1；
Sample Input
3
4 3 3
1 2
2 3
1 3
1 4 10
2 4 20
3 4 30
4 0 3
1 4 10
2 4 20
3 4 30
4 0 2
1 2 100
3 4 100
Sample Output
10
60
-1
以下是我的代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int g[1010][1010];
int visit[1010];
int dis[1010];
int main()
{
int t,n,m,k,i,j,a,b,c;
cin>>t;
while(t--)
{
memset(visit,0,sizeof(visit));
memset(dis,999999,sizeof(dis));
memset(g,999999,sizeof(g));
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
visit[a]=1;
visit[b]=1;
}
for(i=0;i<k;i++)
{
scanf("%d%d%d",&a,&b,&c);
g[a][b]=c;
g[b][a]=c;
if(visit[a]==1&&dis[b]>g[a][b]){
dis[b]=g[a][b];
}
if(visit[b]==1&&dis[a]>g[a][b]){
dis[a]=g[a][b];
}
}
if(m==0){
for(i=2;i<=n;i++){
dis[i]=g[1][i];
}
visit[1]=1;
}
int sum=0;
for(j=1;j<=n;j++)
{
int min=999999;
for(i=1;i<=n;i++)
{
if(dis[i]<min&&!visit[i]){
min=dis[i];
k=i;
}
}
if(min>=999999)break;
visit[k]=1;
sum+=min;
for(i=1;i<=n;i++)
{
if(!visit[i]&&dis[i]>g[i][k]){
dis[i]=g[i][k];
}
}
}
int flag=1;
for(i=1;i<=n;i++)
{
if(!visit[i]){
flag=0;
break;
}
}
if(flag==0)printf("-1\n");
else printf("%d\n",sum);
}
return 0;
}
[解决办法]
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int map[1010][1010];
int visit[1010];
int dis[1010];
int main()
{
int t,n,m,k,i,j,r,a,b,c;
scanf("%d",&t);
while(t--)
{
for(i=0;i<1010;i++)
{
for(j=0;j<1010;j++)
map[i][j]=99999999;
dis[i]=99999999;
visit[i]=0;
}
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
map[a][b]=0;
map[b][a]=0;
}
for(i=0;i<k;i++)
{
scanf("%d%d%d",&a,&b,&c);
map[a][b]=c;
map[b][a]=c;
}
dis[1]=0;
int sum=0;
for(i=1;i<=n;i++)
{
int min=99999999;
for(j=1;j<=n;j++)
{
if(dis[j]<min&&!visit[j])
{
min=dis[j];
r=j;
}
}
if(min>=99999999)break;
sum+=min;
visit[r]=1;
for(j=1;j<=n;j++)
{
if(dis[j]>map[j][r]&&!visit[j])
dis[j]=map[j][r];
}
}
int flag=1;
for(i=1;i<=n;i++)
if(!visit[i])flag=0;
if(flag)printf("%d\n",sum);
else printf("-1\n");
}
return 0;
}
