Given an undirected connected graph of N nodes and M edges. Each node has a light but at a time it can be either green or red. Initially, all the node is of green color. After every T seconds, the color of light changes from green to red and vice-versa. It is possible to travel from node U to node V only if the color of node U is green. The time taken required to travel through any edges is C seconds. Find the minimum amount of time required to travel from node 1 to node N.
Examples:
Input: N = 5, M = 5, T = 3, C = 5
      Edges[] = {{1, 2}, {1, 3}, {1, 4}, {2, 4}, {2, 5}}
Output: 11
Explanation: At 0sec, the color of node 1 is green, so travel from node 1 to node 2 in 5sec.
Now at 5sec, the color of node 2 is red so wait 1sec to change into green.
Now at 6sec, the color of node 2 is green, so travel from node 2 to node 5 in 5sec.
Total time = 5(from node 1 to node 2) + 1(wait at node 2) + 5(from node 2 to node 5) = 11 sec.
Approach: The given problem can be solved by using Breadth-First Search and Dijkstra Algorithm because the problem is similar to the shortest path problem. Follow the steps below to solve the problem:
- Initialize a queue, say Q that stores the nodes that are to be traversed and the time required to reach that node.
- Create a boolean array, say V that stores whether the present node is visited or not.
- Push node 1 and time 0 as a pair in the queue Q.
- Consider that there is always green light and traveling through edges requires 1 second then simply run the BFS and find the shortest time required to reach from node 1 to node N and store it in a variable, say time.
- Create a function findTime which finds the time if traveling through edges requires C seconds and the light color changes after T seconds by performing the following steps:
- Initialize a variable ans as 0 that will store the minimum time required to reach from node 1 to node N.
- Iterate in the range [0, time] using the variable i and perform the following steps:
- If (ans/T) %2 = 1, then modify the value of ans as (ans/T + 1)* T + C.
- Otherwise, add C to the variable ans.
- Print ans as the answer.
Below is the implementation of the above approach: Â
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to find min edgeint minEdge(vector<vector<int> > X,int N, int M, int T, int C) {Â
    // Initialize queue and push [1, 0]    queue<pair<int, int> > Q;    Q.push({1, 0});Â
    // Create visited array to keep the    // track if node is visited or not    vector<int> V(N+1, false);Â
    // Run infinite loop      int crnt, c;    while(1) {               crnt = Q.front().first;          c = Q.front().second;          Q.pop();Â
        // If node is N, terminate loop        if (crnt == N)            break;Â
        // Travel adjacent nodes of crnt        for(int _ : X[crnt]) {            // Check whether we visited previously or not            if (!V[_]) {                               // Push into queue and make as true                Q.push({_, c + 1});                V[_] = true;             }         }    }       return c;}Â
// Function to Find time required to reach 1 to Nint findTime(int T, int C, int c) {Â Â Â Â Â Â Â int ans = 0;Â Â Â Â for (int _ = 0; _ < c; _++) {Â
        // Check color of node is red or green        if ((ans/T) % 2)                        // Add C sec from next green color time            ans = (ans/T + 1)*T + C;        else            // Add C            ans += C;     }         // Return the answer    return ans;}Â
// Driver Codeint main() {Â
    // Given Input    int N = 5;    int M = 5;    int T = 3;    int C = 5;    vector<vector<int> > X{{}, {2, 3, 4}, {4, 5}, {1}, {1, 2}, {2}};Â
    // Function Call    int c = minEdge(X, N, M, T, C);    int ans = findTime(T, C, c);Â
    // Print total time    cout << (ans) << endl;       return 0;}Â
// This code is contributed by Dharanendra L V. |
Java
import java.util.AbstractMap.SimpleEntry;import java.util.ArrayDeque;import java.util.Queue;import java.util.Vector;Â
public class MinEdge {Â
  // Function to find min edge  public static int minEdge(Vector<Vector<Integer> > X,                            int N, int M, int T, int C)  {    // Initialize queue and push [1, 0]    Queue<SimpleEntry<Integer, Integer> > Q      = new ArrayDeque<      SimpleEntry<Integer, Integer> >();    Q.add(new SimpleEntry<Integer, Integer>(1, 0));Â
    // Create visited array to keep the    // track if node is visited or not    Vector<Boolean> V = new Vector<Boolean>(N + 1);    for (int i = 0; i <= N; i++) {      V.add(false);    }Â
    // Run infinite loop    int crnt, c;    while (true) {Â
      crnt = Q.peek().getKey();      c = Q.peek().getValue();      Q.remove();Â
      // If node is N, terminate loop      if (crnt == N)        break;Â
      // Travel adjacent nodes of crnt      for (int i : X.get(crnt)) {        // Check whether we visited previously or        // not        if (!V.get(i)) {Â
          // Push into queue and make as true          Q.add(new SimpleEntry<Integer, Integer>(            i, c + 1));          V.set(i, true);        }      }    }Â
    return c;  }Â
  // Function to Find time required to reach 1 to N  public static int findTime(int T, int C, int c)  {Â
    int ans = 0;    for (int i = 0; i < c; i++) {Â
      // Check color of node is red or green      if ((ans / T) % 2 == 1)Â
        // Add C sec from next green color time        ans = (ans / T + 1) * T + C;      else        // Add C        ans += C;    }Â
    // Return the answer    return ans;  }Â
  // Driver Code  public static void main(String[] args)  {Â
    // Given Input    int N = 5;    int M = 5;    int T = 3;    int C = 5;    Vector<Vector<Integer> > X      = new Vector<Vector<Integer> >();    for (int i = 0; i <= N; i++) {      X.add(new Vector<Integer>());    }    X.get(1).add(2);    X.get(1).add(3);    X.get(1).add(4);    X.get(2).add(4);    X.get(2).add(5);    X.get(3).add(1);    X.get(4).add(1);    X.get(4).add(2);    X.get(5).add(2);Â
    int c = minEdge(X, N, M, T, C);    int ans = findTime(T, C, c);    System.out.println(ans);  }}Â
// This code is contributed by aadityamaharshi21. |
Python3
# Python program for the above approachÂ
# Import library for Queuefrom queue import QueueÂ
# Function to find min edgedef minEdge():Â
    # Initialize queue and push [1, 0]    Q = Queue()    Q.put([1, 0])Â
    # Create visited array to keep the    # track if node is visited or not    V = [False for _ in range(N + 1)]Â
    # Run infinite loop    while 1:        crnt, c = Q.get()Â
        # If node is N, terminate loop        if crnt == N:            breakÂ
        # Travel adjacent nodes of crnt        for _ in X[crnt]:            # Check whether we visited previously or not            if not V[_]:                               # Push into queue and make as true                Q.put([_, c + 1])                V[_] = TrueÂ
    return cÂ
# Function to Find time required to reach 1 to Ndef findTime(c):Â Â Â Â ans = 0Â Â Â Â for _ in range(c):Â
        # Check color of node is red or green        if (ans//T) % 2:                       # Add C sec from next green color time            ans = (ans//T + 1)*T + C        else:            # Add C            ans += C         # Return the answer    return ansÂ
# Driver Codeif __name__ == "__main__":Â
    # Given Input    N = 5    M = 5    T = 3    C = 5    X = [[], [2, 3, 4], [4, 5], [1], [1, 2], [2]]Â
    # Function Call    c = minEdge()    ans = findTime(c)Â
    # Print total time    print(ans) |
C#
using System;using System.Collections.Generic;Â
class Program{    // Function to find min edge    static int MinEdge(List<int>[] X, int N, int M, int T, int C)    {        // Initialize queue and push [1, 0]        Queue<int[]> Q = new Queue<int[]>();        Q.Enqueue(new int[] { 1, 0 });Â
        // Create visited array to keep the        // track if node is visited or not        bool[] V = new bool[N + 1];Â
        // Run infinite loop        int crnt, c;        while (true)        {            int[] arr = Q.Dequeue();            crnt = arr[0];            c = arr[1];Â
            // If node is N, terminate loop            if (crnt == N)                break;Â
            // Travel adjacent nodes of crnt            foreach (int i in X[crnt])            {                // Check whether we visited previously or not                if (!V[i])                {                    // Push into queue and make as true                    Q.Enqueue(new int[] { i, c + 1 });                    V[i] = true;                }            }        }Â
        return c;    }Â
    // Function to Find time required to reach 1 to N    static int FindTime(int T, int C, int c)    {        int ans = 0;        for (int i = 0; i < c; i++)        {            // Check color of node is red or green            if ((ans / T) % 2 == 1)            {                // Add C sec from next green color time                ans = (ans / T + 1) * T + C;            }            else            {                // Add C                ans += C;            }        }Â
        // Return the answer        return ans;    }Â
    static void Main(string[] args)    {        // Given Input        int N = 5;        int M = 5;        int T = 3;        int C = 5;        List<int>[] X = new List<int>[N + 1];        for (int i = 0; i <= N; i++)        {            X[i] = new List<int>();        }        X[1].AddRange(new int[] { 2, 3, 4 });        X[2].AddRange(new int[] { 4, 5 });        X[3].Add(1);        X[4].AddRange(new int[] { 1, 2 });        X[5].Add(2);Â
        // Function Call        int c = MinEdge(X, N, M, T, C);        int ans = FindTime(T, C, c);Â
        // Print total time        Console.WriteLine(ans);    }} |
Javascript
// Function to find min edgefunction minEdge(X, N, M, T, C) {Â
    // Initialize queue and push [1, 0]    let Q = [];    Q.push([1, 0]);Â
    // Create visited array to keep the    // track if node is visited or not    let V = Array(N+1).fill(false);Â
    // Run infinite loop    let crnt, c;    while(true) {               [crnt, c] = Q.shift();Â
        // If node is N, terminate loop        if (crnt === N)            break;Â
        // Travel adjacent nodes of crnt        for(let _ of X[crnt]) {            // Check whether we visited previously or not            if (!V[_]) {                               // Push into queue and make as true                Q.push([_, c + 1]);                V[_] = true;             }         }    }       return c;}Â
// Function to Find time required to reach 1 to Nfunction findTime(T, C, c) {Â Â Â Â Â Â Â let ans = 0;Â Â Â Â for (let _ = 0; _ < c; _++) {Â
        // Check color of node is red or green        if ((ans/T) % 2)                        // Add C sec from next green color time            ans = (ans/T + 1)*T + C;        else            // Add C            ans += C;     }         // Return the answer    return ans;}Â
// Driver Codefunction main() {Â
    // Given Input    let N = 5;    let M = 5;    let T = 3;    let C = 5;    let X = [[], [2, 3, 4], [4, 5], [1], [1, 2], [2]];Â
    // Function Call    let c = minEdge(X, N, M, T, C);    let ans = findTime(T, C, c);Â
    // Print total time    console.log(ans);       return 0;}Â
main();Â
// This code is contributed by aadityamaharshi21. |
Output
11
Time Complexity: O(N + M)
Space Complexity: O(N + M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
