Preparing NOJ

Navi Villages

1000ms 65536K


The Navi villages on Pandora are part of gigantic hometrees. Hometrees specialize in producing

different types of fruits that Navi like to eat. Neytiri’s mother Mo’at asks her to calculate the shortest

path between two given hometrees that allows Mo’at to collect every different type of fruit exactly

once. Your goal is to help Neytiri calculate these paths. Warning: since there are many hometrees on

Pandora, you will not be able to simply examine all possible paths and select the least expensive.


Paths between hometrees are described beginning with the line “GRAPH BEGIN”. Additional

lines lists individual hometrees (nodes), the type of fruit produced by the hometree, the distance to the

neighboring hometrees, followed (on the same line) by their neighboring hometrees (edges). The line

“GRAPH END” ends the list of connection descriptions. The next lines describe pairs of hometrees

for which answers need to be calculated, each on a single line. Following these lines, a completely new

instance of the problem can be given, starting from scratch.

You may assume any hometree can reach any other hometree by some path. Each hometree will

be listed at least once as the first item on some line between the GRAPH BEGIN and GRAPH END.

The same hometree can be listed more than once with different distance values, but it must always

have the same type of fruit assigned to it. Individual connections can appear at most once. It is valid

to list only a hometree and its color (specifying no new connections).

Fruit names will be integers. Not all integers have to be used, however. Your path need only try

to collect fruits that at least one tree grows.


Your output should consist of pairs of hometrees in the same order as in the input, followed

by the length of the shortest path between them that collects each type of fruit exactly once. If such

a path does not exist, you should output “NONE”.

In the first example below, the path a ! b ! c ! d collects all the fruit types (1, 2, 3, and 5) and

the path has length 4.0. No good path exists between a and c, however: the path a ! b ! c ! d ! c

would collect all the fruit types, but it collects fruit 1 twice!

Sample Input:

a 3 1 b e
b 2 2 c
c 1 1 d
d 5
e 2
a d
a c
e 1 2 f
e 1 3 g
f 2
g 2
h 3 4 g f
h e

Sample Output:

a d 4.0
a c NONE
h e 6.0






Provider NOJ

Code NOJ1395


Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10


Nothing Yet