Svemir
Udaljena izvanzemaljska civilizacija želi povezati svoje planete superbrzim podprostornim tunelima. Civilizacija ukupno posjeduje N planeta koje možemo zamisliti kao točke u trodimenzionalnom prostoru. Cijena gradnje tunela između planeta A i [] je CijenaTunela [A,B] = min{ |xA-xB|, |yA-yB|, |zA-zB| } gdje su (xA, yA, zA) koordinata planeta A, dok su (xB, yB, zB) koordinate planeta B. Potrebno je izgraditi točno N-1 tunela i to tako da svaka dva planeta budu izravno ili neizravno povezana tunelima. Vaš posao je da odredite najmanju cijenu gradnje svih tunela zajedno.
InputNa prvom retku ulaza nalazi se jedan prirodan broj N (1 ≤ N ≤ 100000), broj planeta. U sljedećih N redaka nalaze se točno 3 cijela broja po apsolutnoj vrijednosti manjih od 10^9. Ti brojevi predstavljaju x, y i z koordinatu (tim redom) pojedinog planeta.[b] Niti jedna dva planeta se neće nalaziti na potpuno istim koordinatama.
OutputU prvi i jedini redak izlaza potrebno je ispisati minimalnu ukupnu cijenu gradnje N-1 traženog tunela.
Ulaz:
Izlaz:
2
1 5 10
7 8 2Izlaz:
3Ulaz:
Izlaz:
3
-1 -1 -1
5 5 5
10 10 10Izlaz:
11Ulaz:
Izlaz:
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19Izlaz:
4Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.