UVa 11693

From Algorithmist
Jump to navigation Jump to search

Uva 11693 - Speedy Escape[edit]

Problem Link: [1]

Summary[edit]

Given a weighted undirected graph where weights represent distances between vertices (intersections), find the minimum car speed one needs to travel from a fixed starting point to some (at least one) highway entrance (special intersection) without being caught by the police. You know where the police car starts, and know their top speed (160.0 km/h). The minimum speed must guarantee that there is "no way" for the police to catch up with your car.

Explanation[edit]

This problem can be solved in many ways. Here is one:

First of all, one should note that it is always better to use the maximum speed of your car at all times.

Since the graph size is small, you can preprocess the shortest paths between all pairs of vertices using Floyd Warshall algorithm. Use this information to get the minimum time required for the police to travel from their starting point to any other intersection. Note that you can use Dijkstra's algorithm for this step as well since the starting point of the police is fixed.

Now one can binary search the answer! The lower bound of the search is 0 km/h, and pick some large upper bound (1e19 is more than enough). To check if a certain speed works, just use Dijkstra's algorithm to find some path from your starting point to a highway entrance. Dijkstra's algorithm needs to be tweaked a bit in the relaxation phase: do not push an intersection into the heap of possible candidate intersections if you get to it later than the police! Adjust the lower and upper bound accordingly and continue searching.

If the answer diverges to a very large number, state that it is impossible to escape.

Gotchas[edit]

Watch out for precision problems arising from using floating point numbers.

Do not forget to convert distance units according to need.

Notes[edit]

Notice how the algorithm never checks if we cross the police car in the middle of a road (between two intersections)? Try to convince yourself that the way the algorithm works, it is sufficient to check endpoints of the roads only (the intersections).

Input[edit]

3
3 2 1
1 2 7
2 3 8
1
3 2
3 2 1
1 2 7
2 3 8
1
2 3
4 4 2
1 4 1
1 3 4
3 4 10
2 3 30
1 2
3 4

Output[edit]

IMPOSSIBLE
74.6666666667
137.142857143