Given an undirected graph, define the cost of a path as the MEX of all the edge weights on the path. Define $$$dist(u, v)$$$ as minimum possible cost across all paths from $$$u$$$ to $$$v$$$. Practice Problem

• Compute all pairwise distances.
• Given a subset of vertices, find the minimum cost to make them connected. Adding an edge $$$(u, v)$$$ costs $$$dist(u, v)$$$.

I created a video talking about how to solve these in $$$O(N^2 \cdot E)$$$ followed by an optimization for $$$O(N \cdot E)$$$.