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++
// 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.
Python3
# 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)
Publicación traducida automáticamente
Artículo escrito por harshitkap00r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA