/**
     * Resolução do ex 3f
     *
     * @param p personagem que quer conquistar o local
     * @param l local que quer ser conquistado
     * @return uma instancia da classe conquista
     */
    public Conquista consegueConquistarLocal(Personagem p, Local l) {
        if (!(redeLocal.checkVertex(l) || !redeAlianca.validVertex(p))) {//Verifico se o lugar existe e a personagem também
            return null;
        }
        LinkedList<Local> lugaresConquistados = new LinkedList<>();
        for (Personagem aliado : p.getAliados()) {
            if (redeAlianca.getEdge(p, aliado) != null) {
                double forca_alianca = (aliado.getnPontos() + p.getnPontos()) * redeAlianca.getEdge(p, aliado).getWeight(); // (Força_alianca = forcaAliado + forcaPersonagem)*FatorCompatibilidade
                if (l.getDono() != null) {
                    if (!(l.getDono().equals(p))) { //se o alidado nao for dono do local x podemos aplicar o shortPath
                        double forca_necessaria = calcForcaNecessaria(p, aliado, l, lugaresConquistados); //aqui aplica-se um  método parecido com o shortestPath do exercicio 1c
                        if (!(lugaresConquistados.isEmpty())) { //o metodo em cima só preenche o minimo de lugares conquistados  se o aliado nao for dono de nenhum lugar intermédio
                            if (forca_alianca > forca_necessaria && forca_necessaria > 0) {
                                if(l.getDono()!= null){
                                    forca_necessaria += l.getDono().getnPontos();
                                }
                                return new Conquista(aliado, lugaresConquistados,  forca_necessaria,forca_alianca);
                            }
                        }
                    }
                }
            }
        }
        return null;
    }

    /**
     * Calcula a forca necessaria
     *
     * @param p Personagem que quer conquistar o local
     * @param aliado aliado que vai ajudar
     * @param l local que se quer conquistar
     * @param listaLocal lista de locais intermedios
     * @return forca necessaria
     */
    private double calcForcaNecessaria(Personagem p, Personagem aliado, Local l, LinkedList<Local> listaLocal) {
        double min = Double.MAX_VALUE;
        for (Local localConq : p.getLocaisConquistados()) {
            double val = shortPathConquista(aliado, localConq, l, listaLocal);
            if (val < min) {
                min = val;
            }
        }
        //Se a personagem nao tiver nenhum local então nao podemos retornar nada
        if (min == Double.MAX_VALUE) {
            return -1;
        }
        return min;
    }

    /**
     * Inicio do metodo do shortestPathConquista
     *
     * @param aliado personagem aliada a p
     * @param localOrig local que partem as duas personagens
     * @param localDest local que querem conquistar
     * @param lista lista de lugares intermedios
     * @return peso
     */
    private double shortPathConquista(Personagem aliado, Local localOrig, Local localDest, LinkedList<Local> lista) {
        if (redeLocal.checkVertex(localOrig) && (redeLocal.checkVertex(localDest))) {
            boolean[] knownVertices = new boolean[redeLocal.numVertices()];
            int[] verticesIndex = new int[redeLocal.numVertices()];
            double[] minDist = new double[redeLocal.numVertices()];
            lista.clear();
            shortestPathComPesoLocal(aliado, redeLocal.vertices.indexOf(localOrig), knownVertices, verticesIndex, minDist);
            if (minDist[redeLocal.vertices.indexOf(localDest)] != Double.MAX_VALUE) {
                recreatePath(redeLocal, redeLocal.toIndex(localOrig), redeLocal.toIndex(localDest), verticesIndex, lista);
                return minDist[redeLocal.vertices.indexOf(localDest)];

            }
            return -1;
        }
        return -1;

    }

    /**
     * Determine the shortest path to all vertices from a vertex using
     * Dijkstra's algorithm To be called by public short met
     *
     * @param <V>
     * @param <E>
     * @param source
     * @param knownVertices
     * @param verticesIndex
     * @param minDist
     */
    private void shortestPathComPesoLocal(Personagem aliado, int sourceIdx, boolean[] knownVertices, int[] verticesIndex, double[] minDist) {
        Double edge;
        double pesoLocal;
        double pesoPersonagemLocal;
        for (int i = 0; i < redeLocal.numVertices(); i++) {
            minDist[i] = Double.MAX_VALUE;
            verticesIndex[i] = -1;
            knownVertices[i] = false;
        }
        minDist[sourceIdx] = 0;
        while (sourceIdx != -1) {
            knownVertices[sourceIdx] = true;
            for (Local l : redeLocal.directConnections(redeLocal.vertices.get(sourceIdx))) { //each vAdj of vOrig
                edge = redeLocal.getEdge(redeLocal.vertices.get(sourceIdx), l);
                pesoLocal = (double) l.getnPontos();
                pesoPersonagemLocal = 0.0;
                if (l.getDono() != null) {
                    if (l.getDono().equals(aliado)) { //Aqui insere-se o parametro que um aliado nao pode ser dono de nenhum dos locais intermédios
                        edge = Double.MAX_VALUE;
                    } else if (!knownVertices[redeLocal.vertices.indexOf(l)] && minDist[redeLocal.vertices.indexOf(l)] > minDist[sourceIdx] + edge + pesoLocal + pesoPersonagemLocal) {
                        minDist[redeLocal.vertices.indexOf(l)] = minDist[sourceIdx] + edge + pesoLocal + pesoPersonagemLocal;
                        verticesIndex[redeLocal.vertices.indexOf(l)] = sourceIdx;
                    } else {
                        pesoPersonagemLocal = l.getDono().getnPontos();
                    }
                }
            }
            sourceIdx = getVertMinDist(minDist, knownVertices);
        }
    }