Problem: brute3
As time gets closer to Christmas, Christmas town is bustling with activities once again. All the toy factories are busy making toys. Since Santa is well versed with economic theory, the factories in Christmas town are designed to be very specialized—each factory can only make one specific part of a toy. Thus, an important part of the process is to transport the products of one factory to another factory.
Factories in Christmas town are connected by ducts, which can transport toys both way. Note that if a part has to go from factory 1 to factory 3, it is not required that factory 1 and factory 3 to be directly connected. Instead, one may ship the part from factory 1 to factory 2 first, then to factory 3. Your task is to list all paths from a src factory to the dest factory under the following constraints. First, transporting parts between factories takes time, and we do not want to consider paths which takes longer than maxtime time. Secondly, we will not consider any paths which visit the same factories twice since that will be a waste of resources.
Input
There will be multiple test cases in the input file.
Each input will start with two integers n and m, denoting the number of factories in Christmas town and the number of ducts. Factories will be labelled from 1, 2, …, n.
Next come m triplets of integers F1, F2, and T. This means that there is a duct between factory F1 and factory F2 and transporting toys using this duct will take T minutes.
Finally, there will be 3 integers, denoting the src, dest, and maxtime. Refer to problem statement to what these values mean.
The last test case will be followed by a single integer with value '-1'.
Bounds
For each test case, 1 ≤ n ≤ 20, 1 ≤ T ≤ 100, 1 ≤ maxtime ≤ 10000.
You may assume that there will be no test cases with more than 100000 paths.Output
For each test case, display the case number (1, 2, …) on the first line of the output. Then, describe each path found on a line of its own. The path description is preceded by a space character, followed by the time it takes to traverse the path. Then follows a ':' character and another space. Finally, list the factories visited in the path. Separate each factory with a space. Refer to sample output for more details.
When listing the paths, list the paths with shorter duration first. In case of a tie, list the paths in lexicographical order. A path p = (p1, p2, …, pn) is lexicographically smaller than a path q = (q1, q2, …, qn) if there exists an integer k such that p1 = q1, p2 = q2, … p(k-1) = q(k-1), p(k) < q(k). Again, refer to sample output for more details.
If there are no paths, print " NO PATHS FOUND!" after the case number.
Separate consecutive test cases by a blank line.
Sample Input
4 5 1 2 2 1 3 3 1 4 1 2 3 2 3 4 4 1 3 4 4 5 1 2 2 1 3 3 1 4 1 2 3 2 3 4 4 1 4 10 5 7 1 2 2 1 4 5 2 3 1 2 4 2 2 5 3 3 4 3 3 5 2 1 3 8 5 0 1 2 100 -1
Sample Output
Case 1: 3: 1 3 4: 1 2 3 Case 2: 1: 1 4 7: 1 3 4 8: 1 2 3 4 Case 3: 3: 1 2 3 7: 1 2 4 3 7: 1 2 5 3 8: 1 4 2 3 8: 1 4 3 Case 4: NO PATHS FOUND!
HINT: You are allowed to simply find all paths, store them, sort, and print them out in order. The input has been set up so that you will have sufficient memory to store all the paths. Also, note that the maximum number of paths in the graph is small....keep this in mind when you are pruning your search tree.