An honest hint
A navigator team wants to speed up route search by running A* instead of Dijkstra. A colleague has already computed the hint: for every crossroads a number h(v), an estimate of the distance to the finish t. Before this goes into the navigator, the hint has to be checked. If it promises more than the real drive anywhere, A* may return a route that is not the shortest. And if it does not overestimate but breaks the triangle inequality on some road, A* code that does not reopen vertices can go wrong too.
A hint is called consistent if h(t) = 0 and for every road between u and v of length w, h(u) ≤ w + h(v) and h(v) ≤ w + h(u). A hint is called admissible if for every crossroads h(v) ≤ d(v, t), where d is the length of the shortest path by road. If t cannot be reached from v, the distance is infinite and the hint overestimates nothing there.
Determine what kind of hint you have.
Input
The first line holds three numbers n, m, t: the number of crossroads, the number of roads and the finish (1 ≤ t ≤ n ≤ 30,000, 1 ≤ m ≤ 60,000). Then m lines a b w: a two-way road between crossroads a and b of length w metres (1 ≤ w ≤ 106). There may be loops and several roads between one pair. The last line holds n integers h(1), …, h(n), 0 ≤ h(v) ≤ 1012.
Output
One line:
consistentif the hint is consistent;- otherwise
admissible Kif it is admissible, where K is the number of roads on which the inequality is broken (in at least one direction); - otherwise
overestimates K, where K is the number of crossroads with h(v) > d(v, t).
Tests 4 to 8 are the real streets of Almaty with the finish at the Green Bazaar and five different hints.
Examples
Example 1
5 6 5 1 2 4 2 3 3 1 3 6 3 5 5 2 4 2 4 5 7 9 6 4 5 0
consistent
Example 2
5 6 5 1 2 4 2 3 3 1 3 6 3 5 5 2 4 2 4 5 7 11 3 5 6 0
admissible 2
Example 3
5 6 5 1 2 4 2 3 3 1 3 6 3 5 5 2 4 2 4 5 7 9 6 4 8 0
overestimates 1
Limits
- Time · Python
- 6000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
One of the two properties can be checked by looking at each road separately. The other cannot: which one, and why?
2Hint 2
To learn d(v, t) for all v at once you do not need to start a search from every crossroads. The roads are two-way.
3The idea
Consistency is a local property: a condition on each road and on the finish, checked in one pass over the list of roads. Admissibility is global: it compares the hint with the real distances to the finish. One run of Dijkstra from t gives them: the roads are two-way, so the distance from t to v equals the distance from v to t. For a directed graph you would run Dijkstra from t over reversed edges.
4Walkthrough
First check consistency: h(t) = 0 and both inequalities on every road. If everything holds, the answer is consistent, and Dijkstra is not needed: a consistent hint is always admissible. You can see this by adding the inequalities along a shortest path v = v0, v1, …, vk = t: h(v0) ≤ w1 + h(v1) ≤ … ≤ w1 + … + wk + h(t) = d(v, t).
The converse is false, and the second sample shows it. There h(2) = 3, while the real distance from crossroads 2 to the finish is 8: the hint is far too low, so its neighbours 1 and 4 look like “offenders”: 11 > 4 + 3 and 6 > 2 + 3. Nothing is overestimated anywhere, and the answer is admissible 2. If consistency fails, compute the distances from t with Dijkstra and compare.
The fourth test is worth looking at separately. Its hint is the straight-line distance rounded down to a metre, and it seems that this one at least is honest: a road is never shorter than a straight line. But in the data the coordinates of crossroads and the lengths of streets are already rounded to a metre, and at one crossroads, 890 m from the bazaar by road, the straight line between the rounded points gives 891. The answer is overestimates 1, and the triangle inequality is broken on 113 roads. The article on A* discusses this: on real data an “obviously honest” hint can lie by a metre.
4+Solution
5Complexity
Checking consistency is O(m), Dijkstra O((n + m) log n). Starting a search from every crossroads to learn its distance to the finish is O(n · (n + m) log n), and with 30,000 crossroads that is hours.
6Common mistakes
- Checking admissibility road by road. The condition “every road is fine” is consistency. A hint can break it and still overestimate nowhere: the second sample, the seventh and tenth tests.
- Forgetting unreachable crossroads. In the eleventh test the second island is not connected to the finish; the hints there are huge, but the distance is infinite and there is no overestimate.
- Forgetting h(t). The hint at the finish itself must be zero: in the twelfth test h(t) = 1, and that is the only overestimate.
- 32-bit numbers. Hints go up to 1012, and the sum w + h does not fit in 32 bits.