|
|
back to boardWhy this code gives WA#10? Please help. It gives Wrong Answer on test 10. Where is mistake? Maybe some tricky cases? #include <stdio.h> int m[505][505],n; int Prim(); int main() { int k,i,j,a,b,s,temp,x; scanf("%d%d",&n,&k); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { m[i][j]=-1; } } for(i=0;i<k;i++) { scanf("%d%d%d",&a,&b,&s); m[a][b]=m[b][a]=s; } printf("Cost: "); x=Prim(); if(x==1000000000) printf("-1\n"); else printf("%d\n",x); s=1000000000; for(i=1;i<=n;i++) { for(j=1;j<i;j++) { if(m[i][j]!=-1) { temp=m[i][j]; m[i][j]=m[j][i]=-1; x=Prim(); if(x<s) s=x; m[i][j]=m[j][i]=temp; } } } printf("Cost: "); if(s==1000000000) printf("-1\n"); else printf("%d\n",s); return 0; } int Prim() { int dist[505],i,parent[505],s=0,j,nom,d; dist[1]=0; for(i=2;i<=n;i++) { parent[i]=-1; if(m[i][1]!=-1) { parent[i]=1; dist[i]=m[i][1]; } } bool vis[505]={0}; vis[1]=1; for(i=1;i<n;i++) { nom=-1; for(j=1;j<=n;j++) { if(!vis[j] && parent[j]!=-1 && (nom==-1 || dist[j]<d)) { nom=j; d=dist[j]; } } if(nom==-1) break; s+=d; vis[nom]=1; for(j=1;j<=n;j++) { if(!vis[j] && m[j][nom]!=-1 && (parent[j]==-1 || m[j][nom]<dist[j])) { dist[j]=m[j][nom]; parent[j]=nom; } } } for(i=1;i<=n;i++) { if(!vis[i]) return 1000000000; } return s; } |
|
|