| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
读取坐标真的要%lf .......亲身经历 : (#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
//#define LOCAL
using namespace std;
const double INF = 0x3f3f3f3f3f3f3f3f;
struct NODE
{
double x,y;
NODE(int a = 0,int b = 0):x(a),y(b){}
}nodes[1010];
double cost[1010][1010];
double cal_dis(const NODE& a,const NODE& b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
int main()
{
#ifdef LOCAL
freopen("./in.txt","r",stdin);
freopen("./out.txt","w",stdout);
#endif
memset(cost,0,sizeof(cost));
int n,m; scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) scanf("%lf%lf",&nodes[i].x,&nodes[i].y);
for(int i = 1;i <= n;i++)
{
for(int j = i+1;j <= n;j++)
{
cost[i][j] = cost[j][i] = cal_dis(nodes[i],nodes[j]);
}
}
while(m--)
{
int x,y; scanf("%d%d",&x,&y);
cost[x][y] = cost[y][x] = 0;
}
//PRIM
double mincost[1010];
bool used[1010];
fill(used,used+n+1,false);
fill(mincost,mincost+n+1,INF);
mincost[1] = 0;
double res = 0;
while(true)
{
int v = -1;
for(int u = 1;u <= n;u++)
{
if(!used[u] && (v == -1 || mincost[u]<mincost[v])) v = u;
}
if(v == -1) break;
used[v] = true;
res += mincost[v];
for(int u = 1; u <= n;u++) mincost[u] = min(mincost[u],cost[v][u]);
}
printf("%.2f\n",res);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator