PROBLEM LINK:
Editorialist: Jingbo Shang
DIFFICULTY:
Easy
PREREQUISITES:
Tree, Enumeration, BFS, DFS, Floyd-Warshall
PROBLEM:
Given a K-node tree, define the cost of a path is the maximum distance from all K-nodes to this node. Considering all paths between M-special nodes, find the minimum cost path from them.
EXPLANATION:
First of all, given the tree, we can calculate the distance between all nodes (dist[][]). For the simplicity, we can adopt Floyd–Warshall algorithm, which is O(K^3) but easy to implement. Also, you can try BFS or DFS starting from all nodes, which takes only O(K^2).
Second, we need to find all nodes on the path between two nodes u and v. One possible solution is using BFS or DFS again. But it will be much easier to implement as following, by checking the distance (this is based on the edge costs are all positive and thus the distance on tree is actually the shortest path):
if (dist[u][i] + dist[i][v] == dist[u][v]):
node i is on the path between u and v.
After we know the nodes on the path, it is easy to find the distant node by enumerating, since we have dist[][] already.
In summary, the algorithm can be divided into following steps:
- Calculate the distance between all nodes (dist[][]), O(K^3) if Floyd;
- Enumerate possible paths between M special nodes. O(M^2);
- For each possible path, get all nodes on the path and find the distant one. O(K^2) if brute-force.
- Take the minimum.
Therefore, the total time complexity is O(K^3 + M^2K^2).