首页 > 代码库 > hdu1162
hdu1162
#include<cstdio> #include<cmath> #include<climits> #include<algorithm> #define INF 1000000000 using namespace std; struct p { double x,y; }spot[110]; double cost[110][110]; double mincost[110]; bool used[110]; int n; double prim() { for(int i=0;i<n;i++) { mincost[i]=INF; used[i]=false; } mincost[0]=0; double res=0; while(true){ int v=-1; for(int i=0;i<n;i++) if(!used[i]&&(v==-1||mincost[i]<mincost[v])) v=i; if(v==-1) break; used[v]=true; res+=mincost[v]; for(int i=0;i<n;i++) mincost[i] = min(mincost[i], cost[v][i]); } return res; } double dis(p a,p b) { double fa = (a.x-b.x); double fb = (a.y-b.y); return sqrt(fa*fa+fb*fb); } int main() { // int n; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) scanf("%lf%lf",&spot[i].x,&spot[i].y); for(int i=0;i<n;i++) for(int j=i;j<n;j++){ if(i==j) cost[i][j]=INF; else { cost[i][j]=cost[j][i]=dis(spot[i],spot[j]); } } // for(int i=0;i<n;i++){ // for(int j=0;j<n;j++){ // printf("%lf ",cost[i][j]); // } // printf("\n"); // } printf("%.2lf\n",prim()); } // printf("%lf",dis(spot[0],spot[1])); return 0; }
hdu1162
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。