Special Edge

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.

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.

In the diagram, we can observe that there is no direct edge between node 1 and node 3. But we can go from node 1 to node 2 using the normal link of length 2 and then from node 2 to node 3 using the special link of length 2. So the total length will be 4 and we can clearly see that no other path can be smaller than this.

In the diagram, we can observe that there is a direct edge between node 1 and node 3. But we can observe that the path that directly connects node 1 to node 3 is longer than the path that goes from node 1 to node 2 and then from node 2 to node 3. Although lengths of both the special links are smaller than their corresponding normal links, we can choose at most 1 special link. So we go from node 1 to node 2 using a normal link having a length of 3 and then from node 2 to node 3 using a special link having length 2. So, the total length of this path becomes 5 which is the least among all other possible paths.

Using Djikstra's Algorithm

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].

Time Complexity

O(N + M * log N), where ‘N’ is the number of nodes present in the graph and ‘M’ is the number of edges present in the graph.

Dijkstra's algorithm visits every node once (O(N)). Therefore it iterates over each edge in (O(M)), each time accessing the priority queue up to two times in O(logN).

So, the overall complexity becomes O(N + M * log N).

Space Complexity

O(N), where ‘N’ is the number of nodes present in the graph.

We need extra linear space to maintain a boolean array to keep track of nodes that have already been visited. We also need extra space to maintain the priority queue.

Problem statement

Sample Input 1:

Sample Output 1:

Explanation for sample input 1:

Sample Input 2:

Sample Output 2:

Explanation for sample input 2: