Solução por Pedro Racchetti
Conteúdos usados:
Para resolvermos esse problema, iremos usar o algoritmo de Dijkstra, para encontramos o menor caminho. Primeiro, iremos ler o grafo da entrada, e ao guardá-lo, guardaremos também o grafo reverso, ou seja, para toda aresta $$U$$ para $$V$$ com peso $$P$$, no grafo que chamaremos de normal, o grafo reverso terá a aresta $$V$$ para $$U$$ com peso $$P$$.
O quase menor caminho, como descrito no problema, não pode conter arestas que pertençam a um menor caminho. Portanto, podemos retirá-las do grafo, e então usar o algoritmo de Dijkstra, saindo de $$S$$ nesse grafo resultante, guardando as menores distâncias de cada vértice à vértice $$S$$ no vetor $$dfim$$; desse modo, temos que o tamanho do quase menor caminho é $$dfim[D]$$. Porém ainda não sabemos como identificar se uma aresta pertence a um menor caminho.
Para acharmos isso, podemos usar o algoritmo de Dijkstra no grafo original partindo do ponto $$S$$, e guardar as menores distâncias de cada ponto em um vetor (chamaremos-o de $$dnorm$$). Podemos então fazer o mesmo processo no grafo reverso, partindo de $$D$$ (chamaremos o novo vetor de $$drev$$). Perceba que uma aresta de $$U$$ para $$V$$, com peso $$P$$ está em um menor caminho de $$S$$ para $$D$$, se e somente se $$dnorm[U] + drev[V] + P$$ for igual à $$dnorm[D]$$.
Isto é verdade devido ao fato de que o menor caminho de $$S$$ para $$D$$ passando pela aresta $$(U, V)$$ é o mesmo que o menor caminho de $$S$$ para $$U$$, somado ao menor caminho de $$V$$ para $$D$$ e ao peso da aresta, $$P$$. Note que o menor caminho de $$S$$ para $$U$$ é guardado em $$dnorm[U]$$ e o menor caminho de $$V$$ para $$D$$ (que é o mesmo que o menor caminho de $$D$$ para $$V$$ no grafo reverso) está guardado em $$drev[V]$$.
Portanto, basta retirar todas as arestas que satisfazem essa condição, e fazer o processo descrito no segundo parágrafo.
Note que retirar arestas é equivalente a montar um novo grafo, sem essas arestas.
Segue o código, comentado, para melhor compreensão da solução.
| #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); | |
| } | |
| } |
