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;
}