C. Bus Tour
Problem ID: bustour Imagine you are a tourist in Warsaw and have booked a bus tour to see some amazing attraction just outside of town. The bus first drives around town for a while (a long while, since Warsaw is a big city) picking up people at their respec...
Problem Statement
Formatted from the contest statement text, with sample tests broken out into copyable blocks.
Imagine you are a tourist in Warsaw and have booked a bus tour to see some amazing attraction just outside of town. The bus first drives around town for a while (a long while, since Warsaw is a big city) picking up people at their respective hotels. It then proceeds to the amazing attraction, and after a few hours goes back into the city, again driving to each hotel, this time to drop people off. For some reason, whenever you do this, your hotel is always the first to be visited for pickup, and the last to be visited for dropoff, meaning that you have to suffer through two not-so-amazing sightseeing tours of all the local hotels. This is clearly not what you want to do (unless for some reason you are really into hotels), so let’s fix it. We will develop some software to enable the sightseeing company to route its bus tours more fairly—though it may sometimes mean longer total distance for everyone, but fair is fair, right? For this problem, there is a starting location (the sightseeing company headquarters), h hotels that need to be visited for pickups and dropoffs, and a destination location (the amazing attraction). We need to find a route that goes from the headquarters, through all the hotels, to the attraction, then back through all the hotels again (possibly in a different order), and finally back to the headquarters. In order to guarantee that none of the tourists (and, in particular, you) are forced to suffer through two full tours of the hotels, we require that every hotel that is visited among the first bh/2c hotels on the way to the attraction is also visited among the first bh/2c hotels on the way back. Subject to these restrictions, we would like to make the complete bus tour as short as possible. Note that these restrictions may force the bus to drive past a hotel without stopping there (this is not considered visiting) and then visit it later, as illustrated in the first sample input.
Input
The first line of each test case consists of two integers n and m satisfying 3 ≤ n ≤ 20 and 2 ≤ m, where n is the number of locations (hotels, headquarters, attraction) and m is the number of pairs of locations between which the bus can travel. The n different locations are numbered from 0 to n − 1, where 0 is the headquarters, 1 through n − 2 are the hotels, and n − 1 is the attraction. Assume that there is at most one direct connection between any pair of locations and it is possible to travel from any location to any other location (but not necessarily directly). Following the first line are m lines, each containing three integers u, v, and t such that 0 ≤ u, v ≤ n − 1, u 6= v, 1 ≤ t ≤ 3600, indicating that the bus can go directly between locations u and v in t seconds (in either direction).
Output
For each test case, display the case number and the time in seconds of the shortest possible tour.
Sample Input Output for Sample Input
5 4 Case 1: 300
0 1 10 Case 2: 6
1 2 20
2 3 30
3 4 40
4 6
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1Editorial
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/2012/C-bus-tour/solution.texC++ implementationcompetitive_programming/icpc/2012/C-bus-tour/solution.cppStatement textcompetitive_programming/icpc/2012/C-bus-tour/statement.txtStatement PDFcompetitive_programming/icpc/2012/C-bus-tour/statement.pdfMetadatacompetitive_programming/icpc/2012/C-bus-tour/meta.jsonYear packetcompetitive_programming/icpc/2012/contest_problems.pdf