test

10165102128 edited 5 年,1 月前

test

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdio>

using namespace std;

struct path{
    int u, v;
    double dis;
    bool operator <(const path& ano) const{
        return dis > ano.dis;
    }
    path(int u, int v, double dis):u(u), v(v), dis(dis){}
};

vector<path> e;
vector<int> G[1100];
bool vis[1100];
vector<int> v;
pair<int ,int> farm[1100];

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> farm[i].first >> farm[i].second;
    }
    int t = 0;
    for(int i = 0; i < m; i++){
        int temp1, temp2;
        cin >> temp1 >> temp2;
        e.push_back(path(temp1, temp2, 0));
        G[temp1].push_back(t++);
        e.push_back(path(temp2, temp1, 0));
        G[temp2].push_back(t++);
    }
    for(int i = 1; i <= n - 1; i++){
        for(int j = i + 1; j <= n; j++){
            long long dx = farm[i].first - farm[j].first;
            long long dy = farm[i].second - farm[j].second;
            e.push_back(path(i, j, sqrt(dx * dx + dy * dy)));
            G[i].push_back(t++);
            e.push_back(path(j, i, sqrt(dx * dx + dy * dy)));
            G[j].push_back(t++);
        }
    }
    double res = 0;
    v.push_back(1);
    vis[1] = true;
    while(v.size() != n){
        double d = 10000000;
        int next;
        for(int u: v){
            for(int temp: G[u]){
                if(!vis[e[temp].v] && e[temp].dis < d){
                    d = e[temp].dis;
                    next = e[temp].v;

                }
            }
        }
        v.push_back(next);
        vis[next] = true;
        res += d;
    }
    printf("%.2f\n", res);
}

Past Versions

Comments