uva 10397 - Connect the Campus

클릭하여 링크 열기uva10397
제목 뜻: n개의 점을 주고 링크 n개의 최소 경로 길이를 찾아야 합니다
생각: Prime + 최소 스패닝 트리
분석: 간단한 최소 생성 트리 제목, 직접 템플릿을 씌우면
코드:

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define MAXN 1010
#define INF 0xFFFFFFF

int n , m;
double ans;
double G[MAXN][MAXN];
int vis[MAXN];
double lowcost[MAXN];
struct Point{
    double x;
    double y;
}p[MAXN];

void init(){
     for(int i = 1 ; i <= n ;i++){
        for(int j = 1 ; j <= n ; j++){
           double tmp_x , tmp_y;
           tmp_x = (p[i].x-p[j].x)*(p[i].x-p[j].x);
           tmp_y = (p[i].y-p[j].y)*(p[i].y-p[j].y);
           G[i][j] = sqrt(tmp_x + tmp_y);
        }
     } 
}

void Prime(){
    int pos;
    double min;
    ans = 0;
    memset(vis , 0 , sizeof(vis));
    vis[1] = 1;
    for(int i = 1 ; i <= n ; i++)
       lowcost[i] = G[1][i];
    for(int i = 1 ; i <= n ; i++){
       min = INF;
       for(int j = 1 ; j <= n ; j++){
          if(!vis[j] && lowcost[j] < min){
             min = lowcost[j];
             pos = j;
          }
       }
       if(min == INF)
         break;
       ans += min;
       vis[pos] = 1;
       for(int j = 1 ; j <= n ; j++){
          if(!vis[j] && lowcost[j] > G[pos][j])
             lowcost[j] = G[pos][j];
       }
    }
    printf("%.2lf
" , ans);
}

int main(){
    int a , b;
    while(scanf("%d" , &n) != EOF){
        for(int i = 1 ; i <= n ; i++)
           scanf("%lf%lf" , &p[i].x , &p[i].y);
        init();
        scanf("%d" , &m);
        for(int i = 0 ; i < m ; i++){
           scanf("%d%d" , &a , &b);
           G[a][b] = G[b][a] = 0;
        }
        Prime();
    }
}