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.