I. Road Times
Ubol Narongdid is the founder of a brash new startup company called Special D-Liver-E. She wants to corner the market on overnight deliveries of organs between hospitals in the Phuket area. For scheduling purposes it is important to have accurate estimates...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
Ubol Narongdid is the founder of a brash new startup company called Special D-Liver-E. She wants to corner the market on overnight deliveries of organs between hospitals in the Phuket area. For scheduling purposes it is important to have accurate estimates for the times to perform such deliveries. Several trips between various hospitals have already been performed, so delivery times between those pairs of hospitals are known. The company currently has software to estimate times for other (as yet untraveled) trips, but so far all the estimates have been woefully inaccurate. You have been asked to come up with a method to improve these estimates. You have at your disposal the following information: 1) the length (in kilometers) of the roads connecting each pair of cities in the Phuket area, and 2) a set of times (in minutes) for various previously executed deliveries. You know that roads are one-way, and each road has a fixed speed limit that lies between 30 and 60 kilometers per hour. Speed limits are real-valued and need not be integers. You also know that delivery trucks always take the route that minimizes distance traveled, and on each road will always travel at a constant speed equal to that road’s speed limit. Thus you know, for example, that if a given trip is 50 kilometers, the time it will take is between 50 and 100 minutes inclusive, in the absence of any other information. Ah, but you do have other information, namely the times of previous deliveries. It is up to you to use it to produce the best possible estimates.
Input
The input starts with a line containing an integer n (1 ≤ n ≤ 30) indicating the number of cities, numbered 0 to n − 1. After that are n lines each containing n integers specifying the distance in kilometers between cities: the j th value on the ith line indicates the distance when traveling directly from city i to city j. A value of −1 indicates there is no road directly connecting the two cities, and the distance from any city to itself is always 0; all other distances are positive and at most 1 000. There are at most 100 roads. Following this is a line with a single integer r (1 ≤ r ≤ 100) indicating the number of previously executed routes. The next r lines each contain three integers s, d, and t, where s and d are the source and destination cities and t is how long the delivery from s to d took, in minutes. Finally there is a line containing a single integer q (1 ≤ q ≤ 100) indicating the number of future delivery queries. The next q lines each contain two integers s and d giving the source and destination cities for the query. You may assume that for each of the r+q source/destination pairs in the input there is a unique minimum- distance route.
Output
Display a single line for each query containing the source and destination cities for that query, followed by the best low and high bounds on the estimate for the travel time, accurate to within an absolute or relative error of 10−6 .
Sample Tests
3
0 50 -1
55 0 40
-1 40 0
1
0 2 120
3
0 1
1 2
1 00 1 50.0 80.0
1 2 40.0 70.0
1 0 55.0 110.0Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Key Observations
Write the structural observations that make the problem tractable.
State any useful invariant, monotonicity property, graph interpretation, or combinatorial reformulation.
If the constraints matter, explain exactly which part of the solution they enable.
Algorithm
Describe the data structures and the state maintained by the algorithm.
Explain the processing order and why it is sufficient.
Mention corner cases explicitly if they affect the implementation.
Correctness Proof
We prove that the algorithm returns the correct answer.
Lemma 1.
State the first key claim.
Proof.
Provide a concise proof.
Lemma 2.
State the next claim if needed.
Proof.
Provide a concise proof.
Theorem.
The algorithm outputs the correct answer for every valid input.
Proof.
Combine the lemmas and finish the argument.
Complexity Analysis
State the running time and memory usage in terms of the input size.
Implementation Notes
Mention any non-obvious implementation detail that is easy to get wrong.
Mention numeric limits, indexing conventions, or tie-breaking rules if relevant.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
namespace {
void solve() {
// Fill in the full solution logic for the problem here.
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.
Show raw files
competitive_programming/icpc/2016/I-road-times/solution.texC++ implementationcompetitive_programming/icpc/2016/I-road-times/solution.cppStatement textcompetitive_programming/icpc/2016/I-road-times/statement.txtStatement PDFcompetitive_programming/icpc/2016/I-road-times/statement.pdfMetadatacompetitive_programming/icpc/2016/I-road-times/meta.jsonYear packetcompetitive_programming/icpc/2016/contest_problems.pdf