杭电 1871 - 2000 acm的AC解题报告

#include <iostream> #include <cmath> #include <algorithm> using namespace std; struct p { int x,y; }a[200]; int main() { int t,c,i,j,dd; double dis[201],d,sum,map[201][201]; bool visited[201]; cin>>t; while(t--) { cin>>c; for(i = 0;i<c;i++) { for(j = 0;j<c;j++) map[i][j] = 0; dis[i] = 5000; visited[i] = false; } for(i = 0;i<c;i++) { cin>>a[i].x>>a[i].y; for(j = 0;j<i;j++) { dd = (a[i].x - a[j].x)*(a[i].x - a[j].x) + (a[i].y - a[j].y)*(a[i].y - a[j].y); d = sqrt((double)dd); if(d>=10&&d<=1000) map[i][j] = map[j][i] = d; } } sum = dis[0] = 0; while(1) { d = 3000; for(i = 0;i<c;i++) { if(!visited[i]&&dis[i]<d) { d = dis[i]; j = i; } } if(d == 3000) break; sum += d; dis[j] = 0; visited[j] = true; for(i = 0;i<c;i++) { if(!visited[i]&&map[i][j]&&map[i][j]<dis[i]) dis[i] = map[i][j]; } } for(i = 0;i<c;i++) { if(!visited[i]) break; } if(i == c) printf("%.1f\n",sum*100); else printf("oh!\n"); } return 0; }