quasemen.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 512;

struct edge{
        //representaremos as arestas como uma struct
        int de, para, peso;   
        
};
// guardamos os grafos dcomo uma lista de arestas que saem de cada vértice.
vector<edge> gnorm[MAXN]; 
vector<edge> grev[MAXN];
vector<edge> gfim[MAXN];

//guardamos uma lista de todas as arestas, já que teremos de iterar por elas
vector<edge> todas;

int n, m;
int dnorm[MAXN];
int drev[MAXN];
int dfim[MAXN];
int marc [MAXN];

void dijkstranorm(int S){

    //inicializamos o vetor com distâncias como -1,
    //pois essa é a resposta esperada para quando não existe um quase menor caminho
    for(int i = 0; i< n; i++) dnorm[i] = -1;
    dnorm[S] = 0;
   
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int ,int> > >fila;
    fila.push(make_pair(0, S));
    while(true){
        int davez = -1;
       
        while(!fila.empty()){
            int atual = fila.top().second;
            fila.pop();
            if(!marc[atual]){ davez = atual; break;}
        }

        if(davez == -1) break;
        marc[davez] = true;
       
        for(int i = 0; i<(int)gnorm[davez].size();i++){
            edge e = gnorm[davez][i];
    
            if(dnorm[e.para] > dnorm[davez]+e.peso || dnorm[e.para]== -1){
                dnorm[e.para] = dnorm[davez]+e.peso;
                fila.push(make_pair(dnorm[e.para], e.para));         
            }
       
        }              
       
    }
   
}
    
    
void dijkstrarev(int S){
    //inicializamos o vetor com distâncias como -1,
    //pois essa é a resposta esperada para quando não existe um quase menor caminho
    for(int i = 0; i< n; i++) drev[i] = -1;
    drev[S] = 0;
       
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int ,int> > >fila;
    fila.push(make_pair(0, S));
    while(true){
        int davez = -1;
        while(!fila.empty()){
            int atual = fila.top().second;
            fila.pop();
            if(!marc[atual]){ davez = atual; break;}
        }
        if(davez == -1) break;
        marc[davez] = true;
           
        for(int i = 0; i<(int)grev[davez].size();i++){
               
            edge e = grev[davez][i];
            
            if(drev[e.de] > drev[davez]+e.peso || drev[e.de]== -1){
                drev[e.de] = drev[davez]+e.peso;
               
                fila.push(make_pair(drev[e.de], e.de));  
            }
        } 
       
    }
   
}
       
   
 void dijkstrafim(int S){
     //inicializamos o vetor com distâncias como -1,
    //pois essa é a resposta esperada para quando não existe um quase menor caminho

    for(int i = 0; i< n; i++) dfim[i] = -1;
    dfim[S] = 0;
   
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int ,int> > >fila;
    fila.push(make_pair(0, S));
    while(true){
        int davez = -1;
       
        while(!fila.empty()){
            int atual = fila.top().second;
            fila.pop();
            if(!marc[atual]){ davez = atual; break;}
        }
        if(davez == -1) break;
        marc[davez] = true;
       
        for(int i = 0; i<(int)gfim[davez].size();i++){
            edge e = gfim[davez][i];
            
          
            
            if(dfim[e.para] > dfim[davez]+e.peso || dfim[e.para]== -1){
                dfim[e.para] = dfim[davez]+e.peso;
                fila.push(make_pair(dfim[e.para], e.para));                
            }

        }       
    }
           
}
 
void init(){
     for(int i = 0; i<n; i++){
        marc[i] = 0;
        gnorm[i].clear();
        gfim[i].clear();
        grev[i].clear();
        
    }
    todas.clear();


}


int main() {
 
    scanf("%d %d",&n,&m);
    while(n != 0){
        int saindo, chegando;
        scanf("%d %d", &saindo, &chegando );
        init();
        for(int i = 1; i<= m; i++ ){
            int x1, x2, peso;
            scanf("%d %d %d", &x1, &x2, &peso);
            edge e;
            e.de = x1;
            e.para = x2;
            e.peso = peso;
           
            gnorm[x1].push_back(e);
            grev[x2].push_back(e);
            
            todas.push_back(e);
           
        }
        //Fazemos o primeiro dijkstra
        dijkstranorm(saindo);
        
        for(int i = 0; i<n; i++){
            //reinicializamos o vetor de visitados
            marc[i] = 0;           
        }
        //fazemos o segundo dijkstra
        dijkstrarev(chegando);
        
        //criamos o novo grafo, usando apenas as arestas que não pertencem a um menor caminho.
        for(int i = 0; i< todas.size(); i++){
            edge e = todas[i];
            
            if(dnorm[e.de] + e.peso + drev[e.para] != dnorm[chegando]){
                gfim[e.de].push_back(e);        
            }
            
            
        }
        //reinicializamos o vetor de visitados
        for(int i = 0; i<n; i++){
            marc[i] = 0;
        }

        dijkstrafim(saindo);
        // lembre que como inicializamos o vetor de distancias como -1, se não existe um quase menor caminho,
        // iremos imprimir -1.
        printf("%d\n", dfim[chegando]);
        scanf("%d %d", &n, &m);
        
    }
       
   
   
   
   
}