Last Updated: 5 Apr, 2021

Special Edge

Moderate

Asked in companies

Solve now

Problem statement

You are given a list of edges in a graph containing ‘N’ nodes. An edge is made up of two parts, a normal link, and a special link. Both links have their respective lengths. You can use either of the links to travel between two edges. Your task is to determine the shortest distance between the two given nodes such that at most one(possibly, zero) special link is included in this path.

Note:

1. All the edges are directed.

2. Multiple edges can be present between two nodes.

3. The given graph is a single connected component.

4. It does not have any self-loop.

5. At least one path always exists between the two given nodes.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the 'T' test cases follow. 

The first line of each test case contains two space-separated integers ‘N’ and ‘M’, denoting the number of nodes present in the graph and the number of edges present in the graph respectively. Then, ‘M’ lines follow.

Each line contains four space-separated integers, ‘A’, ‘B’, ‘W1’, ‘W2’, denoting that there is a normal link between ‘A’ and ‘B’ having a length ‘D1’ and a special link having a length ‘D2’.

The last line of each test case contains two space-separated integers, ‘X’ and ‘Y’, denoting the nodes between which the shortest distance has to be calculated.

Output Format:

For each test case, return an integer denoting the shortest between the two given nodes.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N < 10^3
N-1 <= M <= 10^3
1 <= A,B,X,Y <= N
1 <= D1,D2 <= 10^6

Time Limit: 1sec

Solve now

Approaches

01 Approach

Approach:

The approach is to apply Dijkstra’s Algorithm after making some modifications according to our requirements. We can make a struct that has three values, the node to which the current node is directed, and the respective distances of both types of edges. We also need a VISITED array to keep track of nodes that have already been VISITED.

Steps:

Create a struct ‘EDGE’ to keep track of all the edges along with the respective distances for each kind of link. Formally, ‘EDGE’ has three values, 'NODE' is the node to which the current edge is directed, 'D1' is the distance of normal link, while 'D2' is the distance of special link.
Create another struct 'QUEUE_LINK'. This will keep track of all links. Formally, 'QUEUE_LINK' has two values, 'NODE' is the node to which the current link is connected, and boolean 'SPECIAL' tells whether the current link is special or not.
Now, define a vector of vectors of class EDGE to form the GRAPH.
Now, define a vector MIN_DIST[2][n+1] to store the shortest distance for all nodes from the source node. Also, define a boolean vector, VISITED[2][n+1] to check whether a node has already been VISITED or not.
Run a loop from ‘i’ = 1 to ‘i’ < ‘N+1’ and do,
1. MIN_DIST[0][i] = INT_MAX
2. MIN_DIST[1][i] = INT_MAX
3. VISITED[0][i] = true
4. VISITED[1][i] = true
Now, initialize a priority_queue ‘PQ’ of 'QUEUE_LINK' class. Make MIN_DIST[0][SRC] = 0 and MIN_DIST[1][SRC] = 0.
Push a new 'QUEUE_LINK'(SRC, 0, false) into ‘PQ’. Also push a new 'QUEUE_LINK'(SRC, 0, true) into ‘PQ’.
In priority queue comparison will be made first on the base of distance(2nd parameter) and then on whether the node is special or not. So a shorter link should be considered first irrespective of its type. If the lengths of the two links are the same, then the special link must be considered first.
Now, while ‘PQ’ is not empty, do:
1. Define ‘CURR_LINK’ = PQ.top() and pop the top element out of ‘PQ’.
2. If ‘CURR_LINK’ > ‘SPECIAL’ = false and VISITED[0][CURR_LINK > NODE] = false, do:
  1. Make VISITED[0][CURR_LINK > NODE] = true.
  2. For each ‘EDGE’ in GRAPH[CURR_LINK > NODE], do:
    1. Make MIN_DIST[0][EDGE.NODE] = min( MIN_DIST[0][EDGE.NODE], MIN_DIST[0][CURR_LINK > NODE] + edge.d1);
    2. Make MIN_DIST[1][EDGE.NODE] = min( MIN_DIST[1][EDGE.NODE], MIN_DIST[0][CURR_LINK>NODE] + edge.d2);
    3. Push a new 'QUEUE_LINK'(EDGE.NODE,MIN_DIST[0][EDGE.NODE],false) into PQ. Also push a new 'QUEUE_LINK'(EDGE.NODE,MIN_DIST[0][EDGE.NODE],true) into PQ.
3. Else if ‘CURR_LINK’ > ‘SPECIAL’ = true and VISITED[1][CURR_LINK > NODE] = false, do:
  1. Make VISITED[1][CURR_LINK > NODE] = true.
  2. For each edge in GRAPH[CURR_LINK > NODE], do:
    1. Make MIN_DIST[1][EDGE.NODE] = min( MIN_DIST[1][EDGE.NODE], MIN_DIST[1][CURR_LINK > NODE] + edge.d1);
    2. Push a new 'QUEUE_LINK'(EDGE.NODE,MIN_DIST[1][EDGE.NODE],true) into ‘PQ’.
Return the minimum value among MIN_DIST[1][DST] and MIN_DIST[1][DST].

Solve now