Submission #1856652

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define inf 100000000000

ll prim(ll n, vector< pair<ll, ll> > locations){
    ll d[n];
    ll ans = 0;
	fill(d, d + n, inf);
	set<pair<ll,ll> > s;
	for(ll i = 0;i < n;i ++){
		s.insert({d[i],i});
	}
	ll v;

	while(!s.empty()){
		v = s.begin() -> second;
		if(d[v] != inf){
            ans+=d[v];
		}
		d[v] = 0;
		s.erase(s.begin());
		for(ll i = 0; i < n; i++){
            ll t1 = locations[i].first;
            ll t2 = locations[v].first;
            ll t3 = locations[i].second;
            ll t4 = locations[v].second;
            if(t1 > t2){t1 -= t2;}
            else{t1 = (t2-t1);}
            if(t3 > t4){t3 -= t4;}
            else{t3 = (t4-t3);}
            ll w = min(t1, t3);
			if(d[i] > w){
				s.erase({d[i], i});
				d[i] = w;
				s.insert({d[i], i});
			}
		}
	}
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, x, y;
    cin >> n;
    vector< pair<ll, ll> > loc;
    for(ll one = 0; one < n; one++){
        cin >> x >> y;
        pair<ll, ll> temp = make_pair(x, y);
        loc.push_back(temp);
    }
    cout << prim(n, loc);
}

Submission Info

Judge Result