|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|3 초||256 MB||67||16||14||21.538%|
After conquering Britannia, the great Roman general Agricola decided all of his new cities should take advantage of the natural springs found aplenty. He appointed his advisor Wessus Waterus to try to find a way to get each town a fresh supply of water.
There are many springs and many towns and between each are the natural hills and valleys of Roman Britain. Wessus doesn’t want to waste the Imperial coin. He has been tasked with linking each town to a spring by a series of aqueducts using as little material as possible. Water, as we know, only flows downhill so any aqueduct must go from a higher point to a lower; intervening hills, springs and towns are no problem since they can be tunnelled through and on. The only requirement is that all aqueduct components start and end on hilltops.
Any spring must only serve one town, but the Romans are clever enough to find a way for aqueducts to pass each other. Roman engineering is excellent, but has its limits: aqueducts can only be of a limited length.
Each hill may only have at most one spring or one town.
Output one line with one real number, denoting the minimum total length of all aqueducts needed to supply each town with fresh water from its own unique spring or IMPOSSIBLE if there is no way to achieve this. Your answer should be correct up to an absolute or relative precision of 10−6.
6 2 2 8 0 0 6 3 4 7 0 8 8 6 8 8 6 0 6 6 4 8 3 4 1 5
4 2 2 3 1 3 2 3 3 2 2 1 1 2 6 1 1 2 3 4