水到家的一道题,居然WA了3次……没注意到距离是double……没有输出的话要输出一行空行
/* author:jxy lang:C/C++ university:China,Xidian University **If you need to reprint,please indicate the source** */ #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #define INF 1E9 using namespace std; double d[751]; double dis[751][751]; bool vis[751]; int near[751]; struct node { int x,y; }; node org[751]; int n; int prim() { double Min,ans=0; int K=n,i,t,now=0; while(K--) { Min=INF; for(i=0;i<n;i++) if(!vis[i]&&d[i]<Min) Min=d[i],now=i; vis[now]=1; if(now) { ans+=Min; if(Min)printf("%d %d\n",now+1,near[now]+1); } for(i=0;i<n;i++) { if(vis[i]||d[i]<=dis[now][i])continue; d[i]=dis[now][i];near[i]=now; } } return ans; } int main() { int i,j,m,a,b,T=0; while(~scanf("%d",&n)) { memset(vis,0,sizeof(vis)); memset(d,127,sizeof(d)); for(i=0;i<n;i++) scanf("%d%d",&org[i].x,&org[i].y); for(i=0;i<n;i++) for(j=0;j<=i;j++) dis[j][i]=dis[i][j]=sqrt((org[i].x-org[j].x)*(org[i].x-org[j].x)+(org[i].y-org[j].y)*(org[i].y-org[j].y)); scanf("%d",&m); for(i=0;i<m;i++) { scanf("%d%d",&a,&b); dis[a-1][b-1]=dis[b-1][a-1]=0; } if(!prim())puts(""); } }