PROBLEM LINK:
Author: Vaibhav Gosain
Tester: Sameer Gulati
Editorialist: Vaibhav Gosain
DIFFICULTY:
easy-medium
PREREQUISITES:
shortest path, Dijkstra Algorithm
PROBLEM:
Consider a weighted, undirected and connected graph with N nodes, numbered 1 to N, and M edges. Find the minimum cost of any walk from node S to node T , via node V, where cost of a walk is the sum of weights of distinct edges occurring in the walk.
EXPLANATION:
Suppose we take a path P1 from S to V , and a path P2 from V to T. There can be some common edges among these 2 paths. Suppose we reach node U after traversing the last edge in P2 which is common with P1. We can see that in the optimal case, all edges of P2 before node U must also lie in P1 because any other P2 will contribute more cost to the walk.
Hence, the optimal path will always have the following form:
for any node U, the walk consists of edges on the shortest path from S to U, from V to U, and from T to U.
Hence, if dist(a,b) is the cost of shortest path between node a and b, the required minimum cost walk will be:
min{ dist(S,U) + dist(V,U) + dist(T,U) } for all U
The Minimum distance of all nodes from S, T, and V can be found be doing Dijkstra from these 3 nodes.
Time complexity: O((N+M)*logN)
AUTHOR’S SOLUTION:
Author’s solution can be found here.