39 - ZOJ Monthly, September 2005 - 1006
So this is the second version of FatMouse and his favorite food, JavaBean -- boy he just cannot have enough of it, can he? Again FatMouse was lucky enough to find a map of another storehouse which contains JavaBean. The map showed several scattered rooms storing JavaBeans and the rooms were connected by some tunnels. Amount of JavaBeans in each room and the length of each tunnel between any pair of rooms were marked on the map. After some negotiations FatMouse finally had a cat agree to clear two of the rooms' guards for him to enter and leave, under the condition that he had to leave as soon as possible from the other end. Now he comes to you with his map, asking if you could tell him the path for getting the maximum amount of JavaBeans.
Input consists of several test cases.
For each test case, print in the first line two numbers: the number of different paths that satisfy his agreetment with the cat, and the maximum amount of JavaBeans FatMouse can possibly take. Then in the second line, print the rooms on the path which bring him the maximum profit, from Rm1 to Rm2. It is guaranteed that this path is unique since I am too lazy to write up a special judge program :)
5 6 0 2 1 2 1 5 3 0 1 1 0 2 2 0 3 1 1 2 1 2 4 1 3 4 1 1 0 0 0 2Sample Output:
2 4 0 1 2 1 2 0
Author: CHEN, Yue