Super Mario 169
Time limit3sMemory limit256 MB
Choose the switch order and the coin pickup routes in 3D so Mario collects every coin with the least total swim distance.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Geometry, Bit manipulation
- Solved
- No attempts yet
Problem
Siggy likes video games, and lately he has been playing Super Mario 169, the little known sequel to Super Mario 64. The whole game takes place in an ocean, which can be modelled with a 3 dimensional coordinate system. The player swims around as Mario and has to collect every coin. A stage holds up to 169 coins.
The coins are not in plain sight. The ocean holds up to 13 switches, and Mario presses a switch by touching it. Pressing a switch makes up to 13 coins appear. Each switch can be pressed only once. The moment a switch is pressed, every coin revealed by the previously pressed switch that Mario has not picked up yet disappears, and he can never collect it. Switches and coins are small enough to be treated as points.
Mario has to collect every coin, so he presses all switches, and before pressing the next switch he picks up every coin the current switch revealed. Siggy wants the smallest distance Mario has to swim.
Input
The input holds several test cases. Each test case begins with a single line with four integers:
n mx my mz
where () is the number of switches, and the point is Mario's starting point.
The following pattern is then repeated times, once for each switch. The pattern begins with a single line with four integers:
k sx sy sz
where () is the number of coins revealed by this switch, and the point is where the switch sits. After that come lines with three integers each:
cx cy cz
where is the position of one coin revealed by this switch.
Every coordinate satisfies . Within one test case, Mario's starting point, the switch positions and the coin positions are all distinct. The input ends with a line holding four zeros.
Output
For each test case, print the minimum distance Mario has to travel to collect all of the coins, one number per line. Round to exactly two decimal places and print both of them. Print no spaces and no blank lines.