Solução Informática - Nível Intermediário - Semana 2

Solução por Pedro Racchetti

Conteúdos usados:

Algoritmo de Dijkstra

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);

	}





	}

view raw

quasemen.cpp

hosted with ❤ by GitHub