MINWALK - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

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.

2

My approach was to find shortest path from S to V and then update the weights of all edges in that path to 0 (Because if we visit them again they won’t cost anything). Then simply find the shortest path from V to T on the updated graph.
I coded this logic but it gives WA. Is my logic wrong, or implementation, or both?

1 Like
3

@prayushd my approach is the same but this logic is wrong because it’s not necessary to travel to v from s using the shortest path and then update all edges used, more common edges between two paths can reduce total cost.