地址：http://acm.hdu.edu.cn/showproblem.php?pid=3371
其实就是最小生成树，但是这其中有值得注意的地方：就是重边。题目没有告诉你两个城市之间只有一条路可走，所以两个城市之间可能有多条路可以走。
举例： 输入可以包含 1 2 3 // 1到2的成本为3
1 2 5 //1到2的成本为5
因此此时应选成本较低的路。
然后，已经连通的城市之间的连通成本为0。
这题用G++提交得到984ms的反馈，用C++提交则得到484ms的反馈。
很想知道这个时间差是怎么回事。
另外，这题一定还可以优化。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std; const int maxn = 500+10;
int dis[maxn][maxn]; //存两地间的距离
bool vis[maxn]; //是否已经加入树
int temp[maxn];
int shortP[maxn];
const int INF = 65523655;
int n,m,k; inline void input() //初始及输入
{
cin>>n>>m>>k;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
dis[i][j]=INF;
int p,q,r;
while(m--)
{
scanf("%d%d%d",&p,&q,&r);
if( r<dis[p][q] ) //这一句保证存入的是两地间距离的最小值
dis[p][q]=dis[q][p]=r;
}
int t;
memset(temp,0,sizeof(temp));
while(k--)
{
scanf("%d",&t);
for(i=1;i<=t;i++)
scanf("%d",&temp[i]);
for(i=1;i<=t;i++)
for(j=i+1;j<=t;j++)
dis[ temp[i] ][ temp[j] ]=dis[ temp[j] ][ temp[i] ]=0;
}
memset(vis,false,sizeof(vis));
for(i=1;i<=n;i++)
shortP[i]=INF;
} inline int span() //求最低成本
{
int cost=0;
int pos=1,k;
int count=0;
int i,minC=INF;
vis[1]=true;
while(count<n-1) //判断最小生成树是否已经完成
{
for(i=1;i<=n;i++)
if( !vis[i] && shortP[i] > dis[pos][i] )
shortP[i]=dis[pos][i];
k=-1;
minC=INF;
for(i=1;i<=n;i++)
if( !vis[i] && minC > shortP[i] )
{
minC=shortP[i];
k=i;
}
if(k==-1)
return -1; //判断是否还可以再把一个城市加进来
cost += shortP[k];
vis[k]=true;
pos=k;
count++;
}
return cost;
} int main()
{
int T;
while(cin>>T)
{
int flag;
while(T--)
{
input();
flag = span();
cout<<flag<<endl;
}
}
return 0;
}