10397 - Connect the Campus--最短路1AC

#include<cstdlib>#include<iostream>#include<sstream>#include<cstdio>#include<cmath>#include<cstring>#include <algorithm>#include<vector>#include<set>#include<queue>#define LL long long#define inf 0x7fffffff#define E 1e-9#define M 100#define N 751using namespace std;struct point{    int x,y;};struct Node{    int x,y;    double len;};Node node[N*N];int n,m;int p[N];point f[N];double ma[N][N];void init(){    for(int i=0; i<N; i++)        p[i]=i;}int tou(int x){    if(p[x]!=x)        p[x]=tou(p[x]);    return p[x];}double length(point p1,point p2){    return sqrt((p1.y-p2.y)*(p1.y-p2.y)+(p1.x-p2.x)*(p1.x-p2.x));}bool cmp(Node a,Node b){    return a.len<b.len;}int main(){#ifndef ONLINE_JUDGE    freopen("ex.in","r",stdin);#endif    while(scanf("%d",&n)!=EOF)    {        int x,y;        memset(ma,0,sizeof(ma));        init();        for (int i=0; i<n; i++)            scanf("%d%d",&f[i].x,&f[i].y);        scanf("%d",&m);        int fax,fay;        for (int i=0; i<m; i++)        {            scanf("%d%d",&x,&y);            x--,y--;            ma[x][y]=ma[y][x]=-1;            fax=tou(x);            fay=tou(y);            if(fay!=fax)            p[fax]=fay;        }        int cnt=0;        for(int i=0; i<n; i++)            for(int j=i+1; j<n; j++)                if(ma[i][j]!=-1)                {                    node[cnt].len=length(f[i],f[j]);                    node[cnt].x=i;                    node[cnt].y=j;                    cnt++;                }        sort(node,node+cnt,cmp);//        for(int i=0;i<cnt;i++)//        cout<<node[i].x<<" "<<node[i].y<<" "<<node[i].len<<endl;        double ans=0.0;        for(int i=0; i<cnt; i++)        {            fax=tou(node[i].x);            fay=tou(node[i].y);            if(fax!=fay)            {                p[fax]=fay;                ans+=node[i].len;            }        }        printf("%.2lf\n",ans);    }    return 0;}