http://acm.hdu.edu.cn/showproblem.php?pid=3371
这道题要注意重边。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1000 5 using namespace std; 6 const int inf=1<<30; 7 8 int g[maxn][maxn]; 9 int dis[maxn],a[maxn]; 10 bool vis[maxn]; 11 long long sum=0; 12 int n,m,x,p,q,c,t; 13 14 void inti() 15 { 16 for(int i=0; i<=n; i++) 17 { 18 for(int j=0; j<=n; j++) 19 { 20 if(i==j) g[i][j]=0; 21 else 22 g[i][j]=g[j][i]=inf; 23 } 24 } 25 } 26 27 void prim() 28 { 29 memset(vis,false,sizeof(vis)); 30 for(int i=1; i<=n; i++) dis[i]=g[1][i]; 31 vis[1]=true; 32 dis[1]=0; 33 bool flag=false; 34 for(int i=1; i<n; i++) 35 { 36 int mm=inf,x; 37 for(int y=1; y<=n; y++) if(!vis[y]&&dis[y]<mm) mm=dis[x=y]; 38 vis[x]=true; 39 if(mm==inf) {flag=true;break;} 40 sum+=mm; 41 for(int y=1; y<=n; y++) if(!vis[y]&&dis[y]>g[x][y]) dis[y]=g[x][y]; 42 } 43 if(flag) printf("-1 "); 44 else 45 printf("%lld ",sum); 46 } 47 int main() 48 { 49 int k; 50 scanf("%d",&k); 51 while(k--) 52 { 53 scanf("%d%d%d",&n,&m,&x); 54 inti(); 55 for(int i=0; i<m; i++) 56 { 57 scanf("%d%d%d",&p,&q,&c); 58 if(c<g[p][q]) 59 g[p][q]=g[q][p]=c; 60 } 61 for(int i=0; i<x; i++) 62 { 63 scanf("%d",&t); 64 for(int j=0; j<t; j++) 65 { 66 scanf("%d",&a[j]); 67 } 68 for(int j=0; j<t; j++) 69 { 70 for(int s=0; s<t; s++) 71 { 72 g[a[j]][a[s]]=0; 73 } 74 } 75 } 76 sum=0; 77 prim(); 78 } 79 return 0; 80 }