Dado un gráfico ponderado dirigido representado por un gráfico de array 2-D [][] de tamaño n y 3 enteros src, dst yk que representan el punto de origen, el punto de destino y el número disponible de paradas. La tarea es minimizar el costo del camino entre dos Nodes que contienen como máximo K Nodes en un grafo dirigido y ponderado. Si no existe tal ruta, devuelve -1 .
Ejemplos:
Entrada: n=6, gráfico[][] = [[0, 1, 10], [1, 2, 20], [1, 3, 10], [2, 5, 30], [3, 4, 10], [4, 5, 10]], src=0, dst=5, k=2
Salida: 60
Explicación:
Src = 0, Dst = 5 y k = 2
Puede haber una ruta marcada con una flecha verde que cuesta = 10+10+10+10=40 usando tres paradas. Y la ruta marcada con flecha roja cuesta = 10+20+30=60 usando dos paradas. Pero como puede haber como máximo 2 paradas, la respuesta será 60.
Entrada: n=3, gráfico[][] = [[0, 1, 10], [0, 2, 50], [1, 2, 10], src=0, dst=2, k=1
Salida: 20
Explicación:
Src=0 y Dst=2
Dado que k es 1, entonces se puede tomar el camino de color verde con un costo mínimo de 20.
Aproximación: Aumenta k en 1 porque al llegar al destino se consumirán k+1 paradas. Utilice la búsqueda en anchura para ejecutar el bucle while hasta que la cola se quede vacía. En cada momento , extraiga todos los elementos de la cola y disminuya k en 1 y verifique su lista adyacente de elementos y verifique que no hayan sido visitados antes o que su costo sea mayor que el costo del Node principal + costo de ese Node , luego marcar sus precios por prices[parent] + cost of that node . Si k se convierte en 0luego rompa el bucle while porque se calcula el costo o consumimos k+1 paradas. Siga los pasos a continuación para resolver el problema:
- Aumenta el valor de k en 1.
- Inicialice un vector de par adj[n] y construya la lista de adyacencia para el gráfico .
- Inicializa un vector de precios[n] con valores -1.
- Inicializa una cola del par q[].
- Empuje el par {src, 0} a la cola y establezca el valor de prices[0] como 0 .
- Atraviese un ciclo while hasta que la cola se vacíe y realice los siguientes pasos:
- Si k es igual a 0 , entonces rompa.
- Inicialice la variable sz como el tamaño de la cola.
- Atraviese un bucle while hasta que sz sea mayor que 0 y realice las siguientes tareas:
- Inicialice el Node de variables como el primer valor del par frontal de la cola y el costo como el segundo valor del par frontal de la cola.
- Itere sobre el rango [0, adj[node].size()) usando la variable it y realice las siguientes tareas:
- Si precios[es.primero] es igual a -1 o costo + es.segundo es menor que precios[es.primero] , establezca el valor de precios[es.primero] como costo + es.segundo y empuja el par {es.primero , cost + it.second} en la cola.
- Reduzca el valor de k en 1.
- Después de realizar los pasos anteriores, imprima el valor de prices[dst] como 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 the minimum cost
// from src to dst with at most k stops
int findCheapestCost(int n,
vector<vector<int> >& graph,
int src, int dst, int k)
{
// Increase k by 1 Because on reaching
// destination, k becomes k+1
k = k + 1;
// Making Adjacency List
vector<pair<int, int> > adj[n];
// U->{v, wt}
for (auto it : graph) {
adj[it[0]].push_back({ it[1], it[2] });
}
// Vector for Storing prices
vector<int> prices(n, -1);
// Queue for storing vertex and cost
queue<pair<int, int> > q;
q.push({ src, 0 });
prices[src] = 0;
while (!q.empty()) {
// If all the k stops are used,
// then break
if (k == 0)
break;
int sz = q.size();
while (sz--) {
int node = q.front().first;
int cost = q.front().second;
q.pop();
for (auto it : adj[node]) {
if (prices[it.first] == -1
or cost + it.second
< prices[it.first]) {
prices[it.first] = cost + it.second;
q.push({ it.first, cost + it.second });
}
}
}
k--;
}
return prices[dst];
}
// Driver Code
int main()
{
int n = 6;
vector<vector<int> > graph
= { { 0, 1, 10 }, { 1, 2, 20 }, { 2, 5, 30 }, { 1, 3, 10 }, { 3, 4, 10 }, { 4, 5, 10 } };
int src = 0;
int dst = 5;
int k = 2;
cout << findCheapestCost(n, graph, src, dst, k)
<< endl;
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find the minimum cost
// from src to dst with at most k stops
static int findCheapestCost(int n,
int[][] graph,
int src, int dst, int k)
{
// Increase k by 1 Because on reaching
// destination, k becomes k+1
k = k + 1;
// Making Adjacency List
Vector<pair> []adj = new Vector[n];
for (int i = 0; i < adj.length; i++)
adj[i] = new Vector<pair>();
// U.{v, wt}
for (int it[] : graph) {
adj[it[0]].add(new pair( it[1], it[2] ));
}
// Vector for Storing prices
int []prices = new int[n];
Arrays.fill(prices, -1);
// Queue for storing vertex and cost
Queue<pair > q = new LinkedList<>();
q.add(new pair( src, 0 ));
prices[src] = 0;
while (!q.isEmpty()) {
// If all the k stops are used,
// then break
if (k == 0)
break;
int sz = q.size();
while (sz-- >0) {
int node = q.peek().first;
int cost = q.peek().second;
q.remove();
for (pair it : adj[node]) {
if (prices[it.first] == -1
|| cost + it.second
< prices[it.first]) {
prices[it.first] = cost + it.second;
q.add(new pair( it.first, cost + it.second ));
}
}
}
k--;
}
return prices[dst];
}
// Driver Code
public static void main(String[] args)
{
int n = 6;
int[][] graph
= { { 0, 1, 10 }, { 1, 2, 20 }, { 2, 5, 30 }, { 1, 3, 10 }, { 3, 4, 10 }, { 4, 5, 10 } };
int src = 0;
int dst = 5;
int k = 2;
System.out.print(findCheapestCost(n, graph, src, dst, k)
+"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# python3 program for the above approach
from collections import deque
# Function to find the minimum cost
# from src to dst with at most k stops
def findCheapestCost(n, graph, src, dst, k):
# Increase k by 1 Because on reaching
# destination, k becomes k+1
k = k + 1
# Making Adjacency List
adj = [[] for _ in range(n)]
# U->{v, wt}
for it in graph:
adj[it[0]].append([it[1], it[2]])
# Vector for Storing prices
prices = [-1 for _ in range(n)]
# Queue for storing vertex and cost
q = deque()
q.append([src, 0])
prices[src] = 0
while (len(q) != 0):
# If all the k stops are used,
# then break
if (k == 0):
break
sz = len(q)
while (True):
sz -= 1
pr = q.popleft()
node = pr[0]
cost = pr[1]
for it in adj[node]:
if (prices[it[0]] == -1
or cost + it[1]
< prices[it[0]]):
prices[it[0]] = cost + it[1]
q.append([it[0], cost + it[1]])
if sz == 0:
break
k -= 1
return prices[dst]
# Driver Code
if __name__ == "__main__":
n = 6
graph = [
[0, 1, 10],
[1, 2, 20],
[2, 5, 30],
[1, 3, 10],
[3, 4, 10],
[4, 5, 10]]
src = 0
dst = 5
k = 2
print(findCheapestCost(n, graph, src, dst, k))
# This code is contributed by rakeshsahni
60
Complejidad temporal: O(n*k)
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA