为什么堆优化过不了
查看原帖
为什么堆优化过不了
330985
一只小juruo楼主2020/12/17 12:41
#include<iostream>
using namespace std;
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<iomanip>
struct cmp
{
    bool operator()(pair<long long,int>&p1,pair<long long,int>&p2) const
    {
        return p1.first > p2.first;
    }
};
int main()
{
    int n;
    cin >> n;
    vector<pair<long long,long long>> ve(n);
    for(int i = 0;i < n;i++)
    {
        cin >> ve[i].first >> ve[i].second;
    }
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,cmp> pq;
    vector<long long> dis(n,LONG_LONG_MAX);
    dis[0] = 0;
    map<int,int> helper;
    int count = 0;
    pq.push(make_pair(0,0));
    while(count<n)
    {
        int cur = pq.top().second;
        pq.pop();
        if(helper[cur])
            continue;
        helper[cur] = 1;
        count++;
        for(int i = 0;i < n;i++)
        {
            if(helper[i])
                continue;
            long long d = (ve[i].first-ve[cur].first)*(ve[i].first-ve[cur].first)+(ve[i].second-ve[cur].second)*(ve[i].second-ve[cur].second);
            if(dis[i]>d)
            {
                dis[i] = d;
                pq.push(make_pair(dis[i],i));
            }
        }
    }
    double ans = 0;
    for(int i = 0;i < n;i++)
    {
        ans+=sqrt(dis[i]);
    }
    cout << fixed <<  setprecision(2)<<ans << endl;
}
2020/12/17 12:41
加载中...