VNEMPIRE - Đế chế

Tác giả: RR

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define MAXN 100111
#define oo 1000111000
#define FOR(i,a,b)  for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define FORV(i,v)   for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define P pair<int,int>
#define F first
#define S second
#define MP make_pair
#define PB push_back
using namespace std;

int debug=0;
int n,a[MAXN][3],d[MAXN];
vector< P > ke[MAXN];
P c[MAXN];

void inp() {
    scanf("%d",&n);
    FOR(i,1,n)
        FOR(j,0,2) scanf("%d",&a[i][j]);
}

void init() {
    FOR(j,0,2) {
        FOR(i,1,n) {
            c[i].F=a[i][j];
            c[i].S=i;
        }
        sort(c+1,c+n+1);
        FOR(i,1,n) {
            if (i>1) ke[c[i].S].PB(MP(c[i-1].S,c[i].F-c[i-1].F));
            if (i<n) ke[c[i].S].PB(MP(c[i+1].S,c[i+1].F-c[i].F));
        }
    }
    
    if (debug)
        FOR(i,1,n) {
            FORV(now,ke[i])
                cout<<"("<<now->F<<","<<now->S<<") ";
            cout<<endl;
        }
}

set< P > s;

void modify(int i) {
    FORV(now,ke[i]) {
        int j=now->F, c=now->S;
        if (d[j]<0) continue;
        if (c<d[j]) {
            d[j]=c;
            s.insert(MP(c,j));
        }
    }
}

void solve() {
    FOR(i,1,n) d[i]=oo;
    modify(1); d[1]=-1;
    long long res=0;
    while (!s.empty()) {
        set< P >::iterator it=s.begin();
        int c=it->F, j=it->S; s.erase(it);
        if (c!=d[j]) continue;
        if (d[j]<0) continue;
        d[j]=-1;
        modify(j);
        res+=c;
    }
    cout<<res;
}

int main() {
    inp();
    init();
    solve();
    return 0;
}

Download