You are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge.
Your task is to find the shortest path from a to b satisfying the above condition.
Build 2 copies of a directed graph with only straight edges, and add curved edges from vertex a of graph 1 to vertex b of graph 2, now run dijkstra on the new graph.
You didn't indicate if the graph is directed or undirected. Assuming the graph is undirected I have come up with this following solution:
Run dijkstra from node a. Let's call Da[i] be the shortest path to node i from node a using only straight edges.
Again run dijkstra from node b. Let's call Db[i] be the shortest path to node i from node b using only straight edges.
Let ans be our final answer. Initialize ans by Da[b] because this is the answer for using no curved edges.
So ans=Da[b];
Now for using exactly one curved edge we can check for every edge (u,v) by the following way,
ans=min(ans,Da[u]+weight of curved edge (u,v) +Db[v])
ans=min(ans,Da[v]+weight of curved edge (v,u) +Db[u])
Finally ans will be the answer for using at most one curved edge.
No need to assume it is undirected, The approach works either way.
Found this problem on GFG: Problem Link!