aff

//--------------------------------------------------------------
// NOMES DOS RESPONSÁVEIS: Andrei Oliveira e Chá
//--------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>

// ######### ESCREVA O NROUSP DO PRIMEIRO INTEGRANTE AQUI
char* nroUSP1() {
    return("0000000");
}

// ######### ESCREVA O NROUSP DO SEGUNDO INTEGRANTE AQUI (OU DEIXE COM ZERO)
char* nroUSP2() {
    return("0000000");
}


// elemento das listas de adjacência e de resposta
typedef struct estr {
        int v; // elemento
    int peso; // custo (não precisa ser usado na resposta)
        struct estr *prox;
} NO;

// vertices do grafo (salas) - use este tipo ao criar o grafo
typedef struct
{
       int flag; // para uso na busca em largura e profundidade, se necessario
       bool aberto; // vale true se a sala em questao esta aberta
       NO* inicio;
} VERTICE;


// funcao principal
NO *caminho(int N, int A, int *ijpeso, int *aberto, int inicio, int fim, int chave);

void Dijkstra(int N, int A, int *ijpeso, int inicio, int *dist, int *ant) //Função para fazer o caminho de dijkstra
{
    //INICIALIZAR A MATRIZ!
    int matriz[N][N]; //matriz de AxA arestas, onde o valor na aresta matriz[i][j] é o peso desta aresta;
    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) matriz[i][j] = 999999999;//Inicialização da matriz, recebendo infinito (999999999) como resposta
    //PREENCHER A MATRIZ!
    //A matriz de entrada é a matriz representada pelo ponteiro ijpeso, e tem tamanho 3A, ordenada em ternas {origem, dest, peso};
    int cont = 0; //contador para o preenchimento da matriz;
    int orig = 0; //variável para guardar a origem
    int dest = 0; //variável para guardar o destino
    int peso = 0; //variável para guardar o peso

    while(cont < 3*A) //Enquanto o contador não chegar até o final do vetor...
    {
        orig = ijpeso[cont]; //A origem é sempre o primeiro número da terna
        peso = ijpeso[cont]; //O peso da aresta é sempre o terceiro número da terna
        cont++; //incrementa o contador que marca se a informação é a origem, o destino, ou o peso...
        dest = ijpeso[cont]; //O destino é sempre o segundo número da terna;
        cont++; //incrementa o contador, marcando que o próximo número é o peso;
        peso = ijpeso[cont]; //O peso da aresta é sempre o terceiro número da terna
        matriz[orig][dest] = peso; //Preenche a matriz com a aresta [origem, destino] e peso [peso]
        cont++; //Incrementa o contador, indicando que o próximo número é o começo de outra terna que indica a origem e destino da aresta além de seu peso...
    }
    bool proc[N]; //Marca se um vértice já teve seu custo mínimo determinado pelo algoritmo...
    for(int i = 0; i < N; i++) //Para todos os vértices...
    {
        dist[i] = matriz[inicio][i];  //dist será o peso a aresta do vértice inicio até o vértice i
        proc[i] = false;
        ant[i] = -1;
    }
    dist[inicio] = 0; //A distância até o vértice próprio é zero;
    proc[inicio] = true; //O primeiro vértice já teve seu custo mínimo determinado...
    ant[inicio] = -1; //Início não tem anterior;
    int vert = inicio; //Primeiro vértice a ser verificado;
    while(true){ // repetir pra sempre...

        int menor = 999999999; //Menor distância não foi calculada ainda, ou seja, é infinita;

        //Para cada vértice i adjacente a ...
        for(int i = 0; i < N; i++) {
            if(!proc[i] && dist[i] < menor) {//Se a distância entre o início e este vértice i for menor que a menor distância descoberta até agora...
                vert = i; //O próximo vértice a ser olhado será este, o de menor distância
                menor = dist[i]; //Atualiza a menor distância;
            }
        }


        if(vert == -1) break; //Se não existe nenhum caminho novo a ser olhado, para o algoritmo

        proc[vert] = true; // Marca que a distância mínima do início até o vértice vert foi analisada
        for(int i = 0; i < N; i++){//Para todos os vértices...
            if(dist[i] > (dist[vert] + matriz[vert][i])){ //Se a distância atual de inicio até i for maior que a distância de inicio até o vértice atual mais a distância entre o vértice atual e o vértice i...
                dist[i] = dist[vert] + matriz[vert][i]; //atualiza a nova menor distância de inicio até i como sendo a distância entre inicio e vert mais a distância entre vert e i;
            }
        }
        vert = -1; //Vértice a ser olhado;
    }
}

//------------------------------------------
// O EP consiste em implementar esta funcao
// e outras funcoes auxiliares que esta
// necessitar
//------------------------------------------
NO *caminho(int N, int A, int *ijpeso, int *aberto, int inicio, int fim, int chave)
{
    NO* resp;
    resp = NULL;

    //ENCONTRAR O CAMINHO MÍNIMO == DIJKSTRA!
    int dist[N]; //Variável que guarda as distâncias
    int ant[N]; //Marca o vértice anterior utilizado para se chegar no vértice ant[i];
    Dijkstra(N, A, ijpeso, inicio, dist, ant);
    if(dist[fim] == 999999999) //Se a distância até o final for infinita...
        return resp; //Retorna uma lista vazia: caminho inexistente;
    //Todos os custos mínimos calculados!
    //Verificar agora se o caminho precisa de chave ou não!
    int verif = fim; //Variável para verificar o caminho de mínimo custo realizado;
    bool precisaChave = false; //Variável que determina se o caminho precisa ou não de chave
    while(ant[verif] != 1 || ant[verif] == verif){ //Enquanto a sala verificada tiver anterior... (ou seja, existir anterior...);
        if(!aberto[verif])//Se a sala sendo verificada não estiver aberta...
            precisaChave = true; //Marca este estado;
        verif = ant[verif]; //Define para verificação o vértice o anterior do vértice atual sendo verificado
    }
    //Construir o caminho!
    if(precisaChave) { //Se o caminho mínimo antes encontrado precisa de chave...
        //Devemos usar o caminho já encontrado de custo mínimo até a sala chave...
        //... e depois recalcular um caminho de custo mínimo da sala chave até a sala fim;
        verif = chave; //Começar a construir o caminho de volta, iniciando da sala chave...
        while(ant[verif] != 1 || ant[verif] == verif) //Enquanto o caminho da chave até o inicio tiver anterior...
        {
            if(!aberto[verif]) resp = NULL; //Não existe um caminho destrancado até a sala CHAVE;
            NO* novo = (NO*) malloc(sizeof(NO)); //Novo nó que guardará este vértice no caminho;
            novo->v = verif; //Coloca o vértice atual no nó novo do caminho;
            novo->prox = resp; //Atualiza que o próximo nó do caminho é o caminho até agora
            resp = novo; //Atualiza o primeiro nó do caminho de volta;
            verif = ant[verif];
        }
        //Com o caminho de chave até início construído...
        Dijkstra(N, A, ijpeso, chave, dist, ant); //Calcula o caminho de custo mínimo da sala chave até a sala fim;
        verif = fim; //Começar a construir o caminho de volta, iniciando da sala fim...
        while(ant[verif] != 1 || ant[verif] == verif) //Enquanto o caminho do fim até a sala chave tiver anterior...
        {
            NO* novo = (NO*) malloc(sizeof(NO)); //Novo nó que guardará este vértice no caminho;
            novo->v = verif; //Coloca o vértice atual no nó novo do caminho;
            novo->prox = resp; //Atualiza que o próximo nó do caminho é o caminho até agora
            resp = novo; //Atualiza o primeiro nó do caminho de volta;
            verif = ant[verif];
        }
    }
    else{
        verif = fim; //Começar a construir o caminho de volta, iniciando da sala fim...
        while(ant[verif] != 1 || ant[verif] == verif) //Enquanto o caminho do fim até a sala chave tiver anterior...
        {
            NO* novo = (NO*) malloc(sizeof(NO)); //Novo nó que guardará este vértice no caminho;
            novo->v = verif; //Coloca o vértice atual no nó novo do caminho;
            novo->prox = resp; //Atualiza que o próximo nó do caminho é o caminho até agora
            resp = novo; //Atualiza o primeiro nó do caminho de volta;
            verif = ant[verif];
        }
    }
    return resp;
}



//---------------------------------------------------------
// use main() para fazer chamadas de teste ao seu programa
//---------------------------------------------------------
int main() {


    // aqui vc pode incluir codigo de teste

    // exemplo de teste trivial
    int N=9; // grafo de 3 vértices 1..3
    int aberto[] = {0,1,1,1,1,1,1,1,1}; // todos abertos
    int inicio=7;
    int fim=4;
    int chave=6;
    int A = 18;
    int ijpeso[]={1,2,30,1,3,20,2,1,30,2,6,20,2,7,30,6,2,20,6,7,10,
        7,6,10,
        7,2,30,
        7,3,80,
        7,9,80,
        3,1,20,
        3,7,80,
        3,4,20,
        4,3,20,
        4,9,80,
        9,4,80,
        9,7,80};

    // o EP sera testado com uma serie de chamadas como esta
    NO* teste = NULL;
    teste = caminho(N, A, ijpeso, aberto, inicio, fim, chave);
    while(teste){
        printf("<= V: %i", teste->v);
        teste = teste->prox;
    }
    return 0;
}

// por favor nao inclua nenhum código abaixo da função main()