Tiempo mínimo para llegar del Node 1 al N si se permite viajar solo cuando el Node es Verde

Dado un gráfico conectado no dirigido de N Nodes y M aristas. Cada Node tiene una luz pero a la vez puede ser verde o roja. Inicialmente, todo el Node es de color verde. Después de cada T segundos, el color de la luz cambia de verde a rojo y viceversa. Es posible viajar del Node U al Node V solo si el color del Node U es verde. El tiempo requerido para viajar a través de cualquier borde es C segundos. Encuentre la cantidad mínima de tiempo requerida para viajar del Node 1 al Node N.

Ejemplos:

Entrada: N = 5, M = 5, T = 3, C = 5
           Bordes[] = {{1, 2}, {1, 3}, {1, 4}, {2, 4}, {2, 5 }}
Salida: 11
Explicación: A los 0 segundos, el color del Node 1 es verde, así que viaje del Node 1 al Node 2 en 5 segundos.
Ahora, en 5 segundos, el color del Node 2 es rojo, así que espere 1 segundo para cambiar a verde.
Ahora, a los 6 segundos, el color del Node 2 es verde, así que viaja del Node 2 al Node 5 en 5 segundos.
Tiempo total = 5 (del Node 1 al Node 2) + 1 (esperar en el Node 2) + 5 (del Node 2 al Node 5) = 11 seg.

Enfoque: El problema dado se puede resolver usando Breadth-First Search y Dijkstra Algorithm porque el problema es similar al problema del camino más corto . Siga los pasos a continuación para resolver el problema:

• Inicialice una cola , digamos Q , que almacene los Nodes que se van a atravesar y el tiempo necesario para llegar a ese Node.
• Cree una array booleana, digamos V que almacene si se visita el Node actual o no.
• Empuje el Node 1 y el tiempo 0 como un par en la cola Q.
• Considere que siempre hay luz verde y viajar a través de los bordes requiere 1 segundo, luego simplemente ejecute el BFS y encuentre el tiempo más corto requerido para llegar desde el Node 1 al Node N y guárdelo en una variable, digamos tiempo .
• Cree una función findTime que encuentre el tiempo si viajar a través de los bordes requiere C segundos y el color de la luz cambia después de T segundos realizando los siguientes pasos:
  • Inicialice una variable ans como 0 que almacenará el tiempo mínimo requerido para llegar desde el Node 1 al Node N.
  • Iterar en el rango [0, tiempo] usando la variable i y realizar los siguientes pasos:
    • Si (ans/T) %2 = 1 , entonces modifique el valor de ans como (ans/T + 1)* T + C.
    • De lo contrario, agregue C a la variable ans .
• Escriba ans como la respuesta.

A continuación se muestra la implementación del enfoque anterior:  

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find min edge
int 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 N
int 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 Code
int 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.

# Python program for the above approach
 
# Import library for Queue
from queue import Queue
 
# Function to find min edge
def 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 N
def 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 Code
if __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)

11

Complejidad temporal: O(N + M)
Complejidad espacial: O(N + M)