시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB251619346661835.283%

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

예제 입력 1

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI4ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ODlcdWMxMzEgXHVkMTMwXHViMTEwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWI1NGNcdWIyOTQgMjA0MFx1YjE0NCwgXHVjNzc0XHViYmZjXHVkNjAxXHVjNzQwIFx1YzZiMFx1YzhmY1x1YzVkMCBcdWM3OTBcdWMyZTBcdWI5Y2NcdWM3NTggXHVjNjU1XHVhZDZkXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHVjNjU1XHVhZDZkXHVjNzQwIE5cdWFjMWNcdWM3NTggXHVkNTg5XHVjMTMxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM3NzQgXHVkNTg5XHVjMTMxXHVjNzQ0IFx1ZDZhOFx1YzcyOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM5YzBcdWJjMzBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDU4OVx1YzEzMVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVkMTMwXHViMTEwXHVjNzQ0IFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDU4OVx1YzEzMVx1Yzc0MCAzXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1YzcwNFx1Yzc1OCBcdWQ1NWMgXHVjODEwXHVjNzNjXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YjQ1MCBcdWQ1ODlcdWMxMzEgQSh4PHN1Yj5BPFwvc3ViPiwgeTxzdWI+QTxcL3N1Yj4sIHo8c3ViPkE8XC9zdWI+KVx1YzY0MCBCKHg8c3ViPkI8XC9zdWI+LCB5PHN1Yj5CPFwvc3ViPiwgejxzdWI+QjxcL3N1Yj4pXHViOTdjIFx1ZDEzMFx1YjExMFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NjAgXHViNTRjIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgbWluKHx4PHN1Yj5BPFwvc3ViPi14PHN1Yj5CPFwvc3ViPnwsIHx5PHN1Yj5BPFwvc3ViPi15PHN1Yj5CPFwvc3ViPnwsIHx6PHN1Yj5BPFwvc3ViPi16PHN1Yj5CPFwvc3ViPnwpXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVkMTMwXHViMTEwXHVjNzQ0IFx1Y2QxZCBOLTFcdWFjMWMgXHVhYzc0XHVjMTI0XHVkNTc0XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWQ1ODlcdWMxMzFcdWM3NzQgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YWM4YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWQ1ODlcdWMxMzFcdWM3NDQgXHVkMTMwXHViMTEwXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTg5XHVjMTMxXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQ1ODlcdWMxMzFcdWM3NTggeCwgeSwgelx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAtMTA8c3VwPjk8XC9zdXA+XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVkNTVjIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWQ1ODlcdWMxMzFcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYThcdWI0ZTAgXHVkNTg5XHVjMTMxXHVjNzQ0IFx1ZDEzMFx1YjExMFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4ODciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTVkVNSVIiLCJkZXNjcmlwdGlvbiI6IjxwPkZvdXJ0aCBHcmVhdCBhbmQgQm91bnRpZnVsIEh1bWFuIEVtcGlyZSBpcyBkZXZlbG9waW5nIGEgdHJhbnNjb25kdWl0IHR1bm5lbCBuZXR3b3JrIGNvbm5lY3RpbmcgYWxsIGl0JiMzOTtzIHBsYW5ldHMuIFRoZSBFbXBpcmUgY29uc2lzdHMgb2YgTiBwbGFuZXRzLCByZXByZXNlbnRlZCBhcyBwb2ludHMgaW4gdGhlIDNEIHNwYWNlLiBUaGUgY29zdCBvZiBmb3JtaW5nIGEgdHJhbnNjb25kdWl0IHR1bm5lbCBiZXR3ZWVuIHBsYW5ldHMgQSBhbmQgQiBpczo8XC9wPlxyXG5cclxuPHA+VHVubmVsQ29zdFtBLEJdID0gbWlueyB8eEEteEJ8LCB8eUEteUJ8LCB8ekEtekJ8IH08XC9wPlxyXG5cclxuPHA+d2hlcmUgKHhBLCB5QSwgekEpIGFyZSAzRCBjb29yZGluYXRlcyBvZiBwbGFuZXQgQSwgYW5kICh4QiwgeUIsIHpCKSBhcmUgY29vcmRpbmF0ZXMgb2YgcGxhbmV0IEIuIFRoZSBFbXBpcmUgbmVlZHMgdG8gYnVpbGQgZXhhY3RseSBOIC0gMSB0dW5uZWxzIGluIG9yZGVyIHRvIGZ1bGx5IGNvbm5lY3QgYWxsIHBsYW5ldHMsIGVpdGhlciBieSBkaXJlY3QgbGlua3Mgb3IgYnkgY2hhaW4gb2YgbGlua3MuIFlvdSBuZWVkIHRvIGNvbWUgdXAgd2l0aCB0aGUgbG93ZXN0IHBvc3NpYmxlIGNvc3Qgb2Ygc3VjY2Vzc2Z1bGx5IGNvbXBsZXRpbmcgdGhpcyBwcm9qZWN0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgbnVtYmVyIG9mIHBsYW5ldHMuPFwvcD5cclxuXHJcbjxwPk5leHQgTiBsaW5lcyBjb250YWluIGV4YWN0bHkgMyBpbnRlZ2VycyBlYWNoLiBBbGwgaW50ZWdlcnMgYXJlIGJldHdlZW4gLTEwPHN1cD45PFwvc3VwPiBhbmQgMTA8c3VwPjk8XC9zdXA+IGluY2x1c2l2ZS4gRWFjaCBsaW5lIGNvbnRhaW5zIHRoZSB4LCB5LCBhbmQgeiBjb29yZGluYXRlIG9mIG9uZSBwbGFuZXQgKGluIG9yZGVyKS48XC9wPlxyXG5cclxuPHA+Tm8gdHdvIHBsYW5ldHMgd2lsbCBvY2N1cHkgdGhlIGV4YWN0IHNhbWUgcG9pbnQgaW4gc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBtaW5pbWFsIGNvc3Qgb2YgZm9ybWluZyB0aGUgbmV0d29yayBvZiB0dW5uZWxzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #7 4번