Modified shortest path problem

Question

For a given graph $G=(V,E)$ and a given weight function $W$ lets say we define the new weight for path p to be the regular weight minus the heaviest edge in that path, i.e: $w^*(p)=\varSigma(w(v_i,v_{i+1}) -max\{w(v_i,v_{i+1})) | 1\leq i \leq k$}

The complexity needs to be $O(V+E\log V)$. Obviously i thought about dijkstra, define a new weight function s.t shortest path according to that weight function is the shortest path we looking for, and that just run dijkstra algorithm on the graph using the new weight function, however I cant think about such function, does anyone have an idea? Thanks in advance.

Answer 1

Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need.

Create 2 copies of $G: G_1,G_2$. For every edge $e=(v,u)\in G$ also add an edge $(v_1,u_2)$ between the node $v$ of $G_1$ and $u$ of $G_2$. Make those edge's weight to $0$.

Now, find a shortest path between $s_1$ and $t_2$ (using Djikstra)