Shortest Path Using Atmost One Curved Edge | ASKED IN AN INTERVIEW

Link- https://practice.geeksforgeeks.org/problems/e7d81a082cda6bd1e959d943197aa3bc21b88bdb/1

Given an undirected connected graph of n vertices and list of m 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. If there is no path from a to b, return -1.



Example 1:

Input:
n = 4, m = 4
a = 2, b = 4
edges = {{1, 2, 1, 4}, {1, 3, 2, 4},
         {1, 4, 3, 1}, {2, 4, 6, 5}}
Output:
2

Explanation:
We can follow the path 2 -> 1 -> 4.
This gives a distance of 1+3 = 4 if we follow
all straight paths. But we can take the curved
path  from 1 -> 4, which costs 1. This
will result in a cost of 1+1 = 2

Example 2:
Input:
n = 2, m = 1
a = 1, b = 2
edges = {{1, 2, 4, 1}}
Output :
1

Explanation:
Take the curved path from 1 to 2 which costs 1.

Your Task:
You don't need to read input or print anything. Your task is to complete the function shortestPath() which takes 4 integers n, m, a, and b, and a list of lists named edges of size m as input and returns the cost of shortest path from a to b.


Expected Time Complexity: O((m+n)log(n))
Expected Auxiliary Space: O(n+m)


Constraints:
1 ≤ n,m ≤ 10^5
1 ≤ a,b ≤ n
weight of edges ≤ 10^4

// ------------------------------------------------------------------------------------------------------------------------------------
    struct info{
        int node;
            int wt;
            int curve_wt;
        };


    list<info>* adj;

    int shortestPath(int n, int m, int source, int dest, vector<vector<int>> &edges) {
        adj=new list<info>[n+1];
        for(auto edge: edges){
            adj[edge[0]].push_back({edge[1],edge[2],edge[3]});
            adj[edge[1]].push_back({edge[0],edge[2],edge[3]});
        }
        vector<int> StraightDist(n+1,INT_MAX);
        vector<int> CurvedDist(n+1,INT_MAX);
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

        pq.push({0,source});
        StraightDist[source]=0;
        CurvedDist[source]=0;

        while(!pq.empty()){
            auto curr=pq.top();
            pq.pop();

            int srcNode=curr.second;
            int dist=curr.first;

            for(auto nei: adj[srcNode]){
                if(StraightDist[srcNode] + nei.curve_wt < CurvedDist[nei.node]){
                    // walking straight till srcNode and then using a curved edge
                    CurvedDist[nei.node]=StraightDist[srcNode] + nei.curve_wt;
                    pq.push({CurvedDist[nei.node],nei.node});
                }

                // below are just generic dijsktra logic

                if(CurvedDist[srcNode] + nei.wt < CurvedDist[nei.node]){
                /* this says we had used some curved edge to reach srcNode from source(using 1 curve),
                   check if using a straigt path from srcNode to nei.node is a wise one. Or, the path
                   from src to nei.node using a curved path is already less */
                    CurvedDist[nei.node]=CurvedDist[srcNode] + nei.wt;
                    pq.push({CurvedDist[nei.node],nei.node});
                }

                if(StraightDist[srcNode] + nei.wt < StraightDist[nei.node]){
                  /* this says we had used only straight edge to reach srcNode from source,
                   check if using a straigt path from srcNode to nei.node is a wise one. Or, the path
                   from src to nei.node using a straight path is already less */
                    StraightDist[nei.node]=StraightDist[srcNode] + nei.wt;
                    pq.push({StraightDist[nei.node],nei.node});
                }
            }
        }
        int res=min(CurvedDist[dest],StraightDist[dest]); // checking for both straight and curved
        return res==INT_MAX ? -1 : res;
    }