Save the princess
All submissions for this problem are available.
Princess Leia is trapped in Alderaan. C3PO and R2D2 get in the country to save her. There are bombs kept at various locations which C3PO and R2D2 have been able to figure out.
They don’t know where Princess Leia is, therefore they decide to dispose all the bombs off to ensure her safety. But as they have already used most of their strength in figuring out where the bombs are, they don’t have much strength left and want to dispose all the bombs by moving as less as possible. So they decide to split. They can start at any of the bombs’ locations, but unfortunately the bombs have been programmed such that if a bomb i is diffused after a bomb j with i < j then the ith bomb and all the other remaining bombs get detonated; thereby killing the princess.
Though R2D2 and C3PO have split, they can still communicate with each other. R2D2 uses his analytical skills to figure out a way in which they should proceed, but it is not optimal. You need to help them in saving the princess by minimizing the sum of the total manhattan distance R2D2 travels and the total manhattan distance C3PO travels. You need to output the minimum sum over all possible ways in which they can diffuse all the bombs.
The first line of the input contains an integer T denoting the number of test cases.
First line of each test case is the number of bombs N.
Each of the next n lines contains three space separated integers, where the ith line contains xi yi zi, the coordinates of the ith bomb.
For each test case output a single line containing the minimum sum of the total manhattan distance R2D2 travels and total manhattan distance C3PO travels in order to dispose all the bombs off.
- 1 ≤ T ≤ 100
- 5 ≤ N ≤ 1000
- 0 ≤ x,y,z ≤ 5000
Input: 1 3 2 3 4 0 4 5 3 4 1 Output: 4
C3PO starts at (2,3,4) and R2D2 starts at (3,4,1). C3PO first diffuses the bomb 1, then it moves to (0,4,5) to defuse bomb 2 then C3PO diffuses bomb 3. So the total distance they need to move is 4.
|Time Limit:||0.869565 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions