## TLE '16 Contest 7 P5 - Shortest Path Faster Algorithm

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Java 8 1.6s
Python 3.5s
Memory limit: 512M

Authors:
Problem type
Flaco Lombradi using high-tech instruments to oversee the new freeway system.

Fax McClad, Croneria's least politically active bounty hunter, has just witnessed a revolution on Croneria! The people of Croneria were not satisfied with the high rates imposed on the toll routes present on the Cronerian Toll Route system (even though they sometimes pay users moneys). As a result, the Committee for Charging Cronerians was disbanded and all roads were rebuilt.

The new freeway system is an automated road network with cities, numbered from to , and unidirectional roads. The durability of a road can initially be up to , and decreases by every time a vehicle passes through it. Upon reaching a durability of , the road becomes too bumpy and can no longer be used.

Fax's wingmate, Flaco, is in charge of controlling the automated road network. Every time a vehicle asks for directions, Flaco will determine a path for that vehicle using the least number of roads necessary to travel from a starting city to an ending city. In case of a tie, he picks the lexicographically least path. Obviously, the path must not contain a road with a durability of .

Suppose two paths, and , are both of the same length. Let represent the city on path , and represent the city on path . Path is said to be lexicographically smaller than path if for the smallest where , .

Tomorrow will be an abnormal traffic-heavy day. All vehicles will start at city and want to go to city , but the network is so confusing that all vehicles will ask Flaco for directions. As a result, everybody will move in an entirely predictable manner. Important government officials wish to be prepared for the journey. There will be vehicles containing officials who will ask for a path.

#### Constraints

The durability of any road will not exceed .

1 10
2 20
3 20

#### Input Specification

The first line contains the integers and .

Each of the next lines contain the description of a single uni-directional road. The first two integers, and , indicate that this road connects city to city (and not vice versa). The third integer, , is the durability of this road. At most road connects to .

The next line contains the integer .

Each of the next lines contain a single integer , indicating that an important vehicle will arrive in place in the network. That is, vehicles will have already passed in the network, reducing the durability of some roads.

#### Output Specification

Output lines, with each line describing a list of cities that Flaco should tell the vehicle to take, beginning at and ending at , based on the path selection criteria as described above. If it is impossible to form a path, output Fail.

#### Sample Input

3 6
3 1 1
3 2 2
1 3 1
2 3 1
2 1 2
1 2 2
4
3
2
1
123456789

#### Sample Output

Fail
1 2 3
1 3
Fail