All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Traveling Swamp Thing Problem

Dynamic Programming


Raise them bones!

Swamp Thing feels a disturbance in the Green. It seems that Anton Arcane has once again taken over the Rot and is spreading its evil all over the world. A lot of the world's capital cities are feeling the power of the Rot right now. It is Swamp Thing's duty to preserve a balance between the forces of the Green and the Rot. He must travel to each of the cities affected by the Rot as soon as possible. Luckily, he can use the Green's help to travel to cities through special bidirectional roads. However using the Green to travel from one city to another requires a certain amount of energy. Swamp Thing can only expend a certain amount of energy while travelling.

Swamp Thing wants to travel to all of the world's cities in such an order that the sum of the distances he travels is minimized while the total energy he spends travelling through the Green remains under the maximum energy he can spend.

If such a order of cities does not exist print "-1", else print the minimum distance required to be travelled by Swamp Thing.

Note that Swamp Thing always starts from his swamp whose index is 1 in the input.


Each input file with a line containing three integers, n - the number of cities, m - the number of roads between cities through the Green and E - the amount of energy Swamp Thing can spend.

Then m lines follow, each describing a road. Each road is described in the following format:

u v d e - this represents a bidirectional road from u to v having a distance of d and energy spent will be e.


Print the minimum distance required to be traveled by Swamp Thing to visit all cities while spending energy <= E. If no such possible path exists, print -1.


1 <= n <= 14

1 <= m <= n * (n - 1) / 2

1 <= E <= 100

1 <= dist between cities <= 100000

3 3 25
1 2 4 20
2 3 1 20
1 3 10 5

Test #1: Since Swamp Thing has only 25 energy, his only choice is to go from 1 to 3 to 2, the sum of distances of which is 11

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


Initializing Code Editor...
View All Notifications