Hay n ciudades conectadas por m vuelos. Cada vuelo comienza desde la ciudad u y llega a v con un precio w.

Ahora dadas todas las ciudades y vuelos, junto con el src de la ciudad inicial y el dst de destino, su tarea es encontrar el precio más barato de src a dst con hasta k paradas. Si no existe tal ruta, salida -1.

Por ejemplo:

Ejemplo 1:

Entrada:

N = 3,

Bordes = [[0,1,100], [1,2,100], [0,2,500]]

Src = 0, dst = 2, k = 1

Salida: 200 Explicación: El gráfico se ve así:

enter image description here

Aquí está mi código:

class Solution {
public:
    int ans=INT_MAX;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<vector<int>>>g;
        for(auto f:flights)
        {
            int from=f[0];
            int to=f[1];
            int cost=f[2];
            g[from].push_back({to,cost});
        }
        queue<vector<int>>q;
        q.push({src,0,-1});
        while(!q.empty())
        {
             vector<int>curr=q.front();
            q.pop();
            int currCity=curr[0];
            int currCost=curr[1];
            int currK=curr[2];
            
            if(currCity == dst)
            {
                ans=min(currCost,ans);
                continue;
            }
            for(auto x:g[currCity])
            {
                if(currK+1<=K && currCost+x[1]<ans)
                {
                    q.push({x[0],currCost+x[1],currK+1});
                }
            }
            
        }
        if(ans == INT_MAX)
        {
            return -1;
        }
        return ans;
    }
};

Tuve que usar el algoritmo BFS.

Sin embargo, recibí el siguiente error:

Línea 924: Char 9: error de tiempo de ejecución: enlace de referencia al puntero nulo de tipo 'std :: vector , std :: allocator >> '(stl_vector.h) RESUMEN: UndefinedBehaviorSanitizer: undefined-behaviour /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include /c++/8/bits/stl_vector.h:933:9

No puedo averiguar dónde me equivoqué.

Gracias.

0
Chaitanya Gujarathi 24 jun. 2020 a las 17:51

2 respuestas

vector<vector<vector<int>>>g; should be `vector<vector<vector<int>>>g(n);` 

Donde n puede ser cualquier número. porque intentas obtener un índice específico. tienes que intialisze tu vector.

0
Nilesh Solanki 24 jun. 2020 a las 15:08

Mira este código:

        vector<vector<vector<int>>>g;
        for(auto f:flights)
        {
            int from=f[0];
            int to=f[1];
            int cost=f[2];
            g[from].push_back({to,cost});
        }

Inicialmente g es un vector vacío. Lo primero que está haciendo con él es acceder al elemento no existente: g[from].

Lo que probablemente quisiste decir es:

vector<vector<vector<int>>>g(n);

Aquí puede crear un vector 3D con la primera dimensión correctamente inicializada.

Otras consideraciones: utiliza vectores donde eso no es necesario. El hecho de que esté utilizando un número fijo conocido de elementos sin verificar el tamaño real significa que el vector se usa incorrectamente:

            int from=f[0];
            int to=f[1];
            int cost=f[2];

Intente evitar eso utilizando una estructura, tupla, etc. La estructura es más apropiada porque incluso conoce el papel de cada elemento: from, to, cost.

Este código es muy ineficiente:

for(auto x:g[currCity])
    ...

Siempre que g sea un vector 3D, auto x se convierte en una copia completa de cada elemento 2D. Intente eso en su lugar: for(const auto &x:g[currCity]).

0
Dmitry Kuzminov 24 jun. 2020 a las 15:19