Problem : 304 - 買醬油V 之腳踏車問題

Problem Statistics

Solved Member: 23　　Submission: 65　　User Tried: 24

Statement:

梓喵又回來買醬油了！！

自從上一次，梓喵去買醬油之後，你已經被她的醬油噴得滿臉而得到幸福了。(如果你已經AC過這題的話...)

今天梓喵要到艾恩葛朗特這個地區買醬油，但是艾恩葛朗特實在是太特殊了，所有店家都是飄浮在空中的。

而商店與商店之間，都有H-bike(Heuristic-bike)的站。H-bike的計費方式非常特別，價格只和兩個站的座標有關係。

點i,j之間的價格為min{|xi-xj|,|yi-yj|,|zi-zj|}，而且只要付過一次款，三十分鐘內就不用再付錢。

現在梓喵想要騎著H-bike到所有的商店把醬油全部買回來，而且每到商店就要還H-bike，另外梓喵買醬油非常的快，買完所有商店的醬油花不到三十分鐘，所以兩個店家之間的H-bike只需要付一次錢。

請你幫忙梓喵算算看要花多少錢在H-bike上面，如果花的錢越少，梓喵就會越開心，然後就會給你一個AC並且騎H-bike來撞你！

Input:Output:

第一行有一個數字N。(1≤N≤100000)
接下來N行，每行有三個整數，依序表示商店的X座標、Y座標、Z座標。
梓喵位於第一家商店。
所有整數都介於-1000000000~1000000000之間。

輸出一個正整數表示答案。

Sample Input:Sample Output:

SAMPLE A:
2
1 5 10
7 8 2

SAMPLE B:
3
-1 -1 -1
5 5 5
10 10 10

SAMPLE C:
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

SAMPLE A:
3

SAMPLE B:
11

SAMPLE C:
4

Source:

COCI 2009/2010 #7

Problem Setter

ツンデレkevinpttさん

Testdata:

Test	Time	Memory	Score
0-1	1000ms	65536kb
0-2	1000ms	65536kb
0-3	1000ms	65536kb
1	1000ms	65536kb	10
2	1000ms	65536kb	10
3	1000ms	65536kb	10
4	1000ms	65536kb	10
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10

Problem : 304 - 買醬油V 之 腳踏車問題

Problem : 304 - 買醬油V 之腳踏車問題