ACM ICPC World Finals 2016
Shortest judge solution: 3775 bytes. Shortest team solution (during contest): 5056 bytes.
Similarly to problem B, this problem had two independent components, the first of which is a straightforward shortest paths exercise, and the second of which is the core of the problem. In this problem, the second part can be solved using linear programming.
For each edge e in the graph, let us denote by xe the time it takes to traverse edge e. Initially we know that de ≤ xe ≤ 2de where de is the length of the edge. For a source/destination pair (s, t), let us denote by R(s, t) the set of edges on the shortest route from s to t. When we are told that a delivery from si to ti took ai hours, this can be formulated as the equation ∑e∈R(si,ti) xe = ai. Given this information, finding the minimum possible time it could take to go from s to t is then given by the optimum of the following linear program:
min ∑e∈R(s,t) xe
subject to ∑e∈R(si,ti) xe = ai ∀1 ≤ i ≤ r
de ≤ xe ≤ 2de ∀e
Similarly the maximum possible time is obtained by replacing min by max in the linear program.
Thus we have 2q linear programs to solve, each having r + 2e constraints and e variables. The 2q different programs are in fact all over the same polytope, only the objective function differs, which means that if one uses the Simplex algorithm (which is the most natural choice) one only has to run the first phase (finding a feasible solution) once instead of for each of the 2q programs. (But this optimization was not needed to get accepted – the time limit was very lenient.)
As asides, we are very curious to learn the answers to the following questions (which we haven’t been able to answer ourselves – if you figure out the answers, please let us know!):