【UVa】Frogger

Problem here

Solution

自己的石子為點0，目標石子為1
生成MST直到點0點1連通

#include <iostream>
#include <vector>
#include <memory.h>
#include <utility>
#include <string>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
vector<pair<float, pair<int, int> > > edges;
string spp;
float cal(int x1, int x2, int y1, int y2){
    return (float)sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

bool cmp(pair<float, pair<int, int> > a, pair<float, pair<int, int> > b){
    return a.first < b.first;
}

int pre[1000];

int find(int x){
    int r = x;
    while(pre[r] != r){
        r = pre[r];
    }
    int j = x, y;
    while(j != r){
        y = pre[j];
        pre[j] = r;
        j = y;
    }
    return r;
}

void join(int a, int b){
    int fa = find(a);
    int fb = find(b);
    if(fa != fb){
        pre[fa] = fb;
    }
}
int main(){
    int n;
    int count = 1;
    while(cin >> n){
        if(n==0)
            break;
        vector<pair<int , int > > point;
        for(int i = 0; i < n; i++){
            int x, y;
            cin >> x >> y;
            point.push_back(make_pair(x,y));
            for(int j = 0; j < i; j++){
                edges.push_back(make_pair(cal(point[i].first, point[j].first, point[i].second, point[j].second), make_pair(i, j)) );
            }
        }
        cout << "Scenario #" << count++ << endl;

        sort(edges.begin(), edges.end(), cmp);
        for(int i = 0; i < n; i++)
            pre[i] = i;
        for(int i = 0; i < edges.size(); i++){
            if(find(edges[i].second.first)==find(edges[i].second.second))
                continue;

            join(edges[i].second.first, edges[i].second.second);
            if(find(1) == find(0)){
                printf("Frog Distance = %.3lf\n", edges[i].first);
                break;
            }

        }

        edges.clear();
        cout << endl;
        getline(cin, spp);
    }
    return 0;
}