SRM503 Div2 Hard(900) KingdomXCitiesandVillagesAnother

ちょっと違うけど、プリム法。短いものから貪欲に道路を追加していけば良い。

#include <vector>
#include <cmath>
using namespace std;

double dist( int x1, int y1, int x2, int y2 )
{ return sqrt(double(x1-x2)*(x1-x2)+double(y1-y2)*(y1-y2)); }

class KingdomXCitiesandVillagesAnother{public:
double determineLength( vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY )
{
    int N = (int)cityX.size();
    int M = (int)villageX.size();

    vector<bool> conn(M);

    double ans = 0;

    for ( int i=0; i<M; i++ )
    {
        double mind = 1e100;
        int minv = 0;

        for ( int j=0; j<M; j++ )
        if ( ! conn[j] )
        {
            for ( int k=0; k<N; k++ )
            {
                double d = dist(cityX[k],cityY[k],villageX[j],villageY[j]);
                if ( d < mind )
                    mind = d,
                    minv = j;
            }

            for ( int k=0; k<M; k++ )
            if ( conn[k] )
            {
                double d = dist(villageX[k],villageY[k],villageX[j],villageY[j]);
                if ( d < mind )
                    mind = d,
                    minv = j;
            }
        }

        ans += mind;
        conn[minv] = true;
    }

    return ans;
}};