Techniques - Brute force on solution structure

In some problems it is possible to identify some structure in the optimal solution and then we can brute-force on the unknown parts of that that structure for find the optimal solution.

To illustrate this we are going to solve problem E from BAC 2014.

Pickup and Delivery

A futuristic pickup and delivery company is considering the use of translocators in their business. A translocator is a device that allows the user to teleport himself. It has the two following functions:

• Destroy the current portal if one exists and create one at you current location.
• Teleport yourself to the portal. The portal is destroyed.

Note that this means that there can only be one portal at a given time. Both these actions are instantaneous and take no time to execute.

Given an undirected graph with up to $$50000$$ nodes representing road network, the location of the company headquarters H, the pickup location P and the delivery location D, they would like to know what is the minimum time it takes to go from H to P and then to D knowing that you have a translocator available.

Note that you can use the translocator any number of times.

Example:

Suppose the map is given by the following graph. The best solution is to go from $$H$$ to $$D$$ and drop the translocator. Then go to the pickup location $$P$$, pickup the goods and then teleport yourself back to $$D$$. The total time will be $$4$$.

Solving the problem

Since the number of nodes can be up to $$50000$$, it seems to indicate that there should be a linear time solution for this problem.

We need to reason about the structure of the solution. What can we say about the usage of the translocator? Let's analyze the structure of an optimal solution when the translocator is used.

Consider the following figure. It represents the structure of a path with one teleportation. Going from the headquarters $$H$$ to some node $$T$$ where we drop the teleporter then to some other node $$X$$ and from there, teleport back to $$T$$. (The wiggly arrows represent arbitrary paths)

Clearly, the cycle $$(T, \ldots, X, T)$$ a waste of time if we did not pass by the pickup location $$P$$ because it achieved nothing, we just spent some more time to get back to $$P$$.

Therefore the path must have the form: Here again, we can see a useless path: $$(P, \ldots, X, T)$$ is useless since if we wanted to go back to $$T$$, we could have just teleported from $$P$$ to $$T$$ directly. Thus, so far, the optimal path will look like this: The only thing that remains is to go deliver the goods to $$D$$. For the same reason as above, this path will never use a teleport as it would just create a cylce where no progress towards reaching $$D$$ is achieved: (We put in gray the parts of the solution that we already know are optimal)

Therefore, we can conclude that an optimal solution that uses the teleporter will look as follows: In words, we go from the headquarter $$H$$ to some node $$T$$ where we drop the translocator. Then we go to pickup at $$P$$, teleport back to $$T$$ and go to $$D$$ without teleporting.

So we have the structure of the optimal and the only unknown is node $$T$$. Thus one solution is to simply brute force over all possible values of $$T$$, evaluate the cost of that solution and find the minimal one.

Pickup and Delivery

Write a solution for the pickup an delivery problem described above.

Input

• One line with two integers n and m separated by a single space. The first one represents the number of locations and the second one the number of connections between them.
• $$m$$ lines each with two integers $$u_i$$ and $$u_j$$ separated by a single space, indicating that there is a bidirectional road between locations $$u_i$$ and $$u_j$$. You may assume that you will never be given the same road twice and that there exists at most one road between any two locations.
• One line with three itegers $$H$$, $$P$$ and $$D$$ giving the headquarters location, the pickup location and the delivery location, respectivey.

All roads have the same length and take $$1$$ unit of time to traverse.

Constraints

• $$1 \leq n \leq 50000$$
• $$0 \leq m \leq (n^2 - n) / 2$$
• $$0 \leq H, P, D < n$$
• $$S \neq H, S \neq D, P \neq D$$
• $$0 \leq u_i < n$$
• The graph is connected.

Output

A single line with the minimum travel time.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2

Max file size: 1.0MB
Allowed extensions: .java, .cpp, .py