Driving ------- Its 2200 and the Earth is very much too hot so the good old USA has moved to D-dimensional space, or D-space, somewhere in the Ort Cloud. However, things are not that different from today. There are still towns and cities and roads (running through road-tubes) in between. Actually, its a little more like 1922, before Route 66 was established (in 1926), in that there are no super-highways. You just drive from town to town. Distances are still measured in miles, and as automatic driving did not survive the (lidar) Chaff Anarchists, your car must have a driver. You are driving with friends from New San Francisco to New New York City. You agree that you will only change drivers at a town and you define a `shift' to be the part of the route that one driver drives at a time. You further agree that (1) each shift will drive a shortest route from its initial town to its final town (2) each shift but the last will drive at least M0 miles (3) each shift will drive at most M1 miles (4) the number of shifts S will be as small as possible, given the above (5) S will not be greater than S0 (6) M1 will be as small as possible given the above You want to figure out good values for M0, S0, M1, S, and also plan your route. You have decided to write a program that given M0 and S0 will compute M1 and S and a route. Input ----- For each test case, first a line that gives the test case name. Then a line of the form T R Q D where T is the number of towns, R the number of roads, Q the number of queries, and D the dimension of D-space. Towns are numbered 1, 2, ..., T, where 1 is New San Francisco and T is New New York City. Then R road description lines follow, each of the form: I J M describing a road from Town I to Town J that is M miles long and does not go through any other towns. There is at most one road between any two towns, and no road connects a town to itself. Lastly Q query lines follow, each of the form M0 S0 where M0 and S0 are as describe above. The data is such that there is a path between any two towns, i.e., the graph of towns and roads is connected. The road lengths are close to straight line distances, but in D-space of course. All input numbers are integers. 2 <= T <= 5,000 1 <= R <= 20,000 1 <= Q <= 100 2 <= D <= 10 1 <= M0 <= M1 <= 1,000 1 <= S0 <= 100 1 <= I,J <= T I != J 1 <= M <= 200 Sum R*T+Q*T^2 over all test cases in one file <= 40,000,000 Input ends with an end of file. Test case name lines are at most 80 characters. Output ------ For each test case, first an exact copy of the test case name line. Then for each query description line one output line containing M0 S0 M1 S T1 T2 ... TS where M0 and S0 are copied from the query description line, M1 is the smallest possible value of M1 given M0 and S0, S is the smallest possible number of shifts given M0 and M1, and T1, T2, ..., TS are the numbers of the DESTINATION towns of the consecutive shifts in the route. Necessarily S <= S0 and TS == T. If there is more than one route for a given M1 and S, any one will do. Sample Input ------ ----- -- SAMPLE 1 -- 5 5 12 2 1 2 10 2 3 10 3 4 10 4 5 10 1 3 15 5 10 5 20 10 1 10 2 10 3 10 4 20 1 20 2 20 3 30 1 30 2 30 3 -- SAMPLE 2 -- 12 15 11 2 1 12 100 1 2 90 2 12 90 1 3 80 3 4 80 4 12 80 1 5 70 5 6 70 6 7 70 7 12 70 1 8 60 8 9 60 9 10 60 10 11 60 11 12 60 50 1 50 2 50 3 50 4 50 5 50 6 60 6 70 6 80 6 90 6 100 6 Sample Output ------ ------ -- SAMPLE 1 -- 5 10 10 4 2 3 4 5 5 20 10 4 2 3 4 5 10 1 35 1 5 10 2 20 2 3 5 10 3 15 3 3 4 5 10 4 10 4 2 3 4 5 20 1 35 1 5 20 2 25 2 4 5 20 3 25 2 4 5 30 1 35 1 5 30 2 35 1 5 30 3 35 1 5 -- SAMPLE 2 -- 50 1 100 1 12 50 2 90 2 2 12 50 3 80 3 3 4 12 50 4 70 4 5 6 7 12 50 5 60 5 8 9 10 11 12 50 6 60 5 8 9 10 11 12 60 6 60 5 8 9 10 11 12 70 6 70 4 5 6 7 12 80 6 80 3 3 4 12 90 6 90 2 2 12 100 6 100 1 12 File: driving.txt Author: Bob Walton Date: Wed Aug 8 04:14:51 EDT 2018 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.