Solução Mania de Par

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

Este problema é uma adaptação muito simples do algoritmo de Dijkstra. Basta guardarmos não só a menor distância para uma determinada cidade, mas a menor distância passando por um número par de pedágios e a menor passando por um número ímpar.

Seja $dist[v]$ um par de inteiros cujo primeiro elemento é a menor distância da origem a $v$ que passa por um número par de pedágios e o segundo, por um número ímpar. Agora, para executarmos o Dijkstra, basta fazermos dois tipos de atualização. Suponha que estamos na cidade $v$ olhando o vizinho $u$ , cuja distância é $d$ . Para atualizarmos a distância ímpar de $u$ , verificamos de $d+dist[v].F<dist[u].S$ , pois $dist[v].F$ passa por um número par de pedágios, logo, ao passarmos pela estrada $v - u$ , adicionamos um pedágio e agora temos um número ímpar. Atualizamos o número par de maneira análoga.

No fim, basta imprimirmos a resposta, que está salva na distância par ao destino. Segue o código para melhor entendimento.

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	#include <queue>

	using namespace std;

	#define F first
	#define S second
	#define PB push_back

	#define MAXN 10100
	#define INF 0x3f3f3f3f

	typedef pair<int,int> ii;

	vector<ii> lista[MAXN];

	int c, v;

	// algoritmo de Dijkistra modificado
	int dijkstra(int ori, int dest){

	// vetor de distâncias modificado (guarda pares)
	ii dist[MAXN];

	// infinito o vetor de distâncias
	for(int i=1; i<=c; i++) dist[i]=ii(INF,INF);

	// a distância par de 1 a C é 0 (passa por zero pedágios)
	// e a diastância ímpar é INF (pois não existe)
	dist[1]=ii(0,INF);

	// heap de prioridades
	priority_queue< ii, vector<ii>, greater<ii> > heap;

	// adiciono a cidade 1 a distância 0
	heap.push(ii(0,1));

	// enquanto a heap não estiver vazia
	while(!heap.empty()){

	int v=heap.top().S, d=heap.top().F; heap.pop();

	// se d supera as duas distâncias, está desatualizado
	if(d>dist[v].F and d>dist[v].S) continue;

	// para cada vizinho de v
	for(int i=0; i<lista[v].size(); i++){

	ii u=lista[v][i];

	// checo se consigo melhorar a distância ímpar até u
	if(dist[v].F+u.S<dist[u.F].S){

	dist[u.F].S=dist[v].F+u.S;

	heap.push(ii(dist[u.F].S, u.F));
	}

	// ou a distância par
	if(dist[v].S+u.S<dist[u.F].F){

	dist[u.F].F=dist[v].S+u.S;

	heap.push(ii(dist[u.F].F, u.F));
	}
	}
	}

	// se não consigo alcançar o destino
	// com quantidade par de pedágios, retorno -1
	if(dist[dest].F==INF) return -1;

	// caso contrário, retorno a distância
	return dist[dest].F;
	}

	int main(){

	// leio o destino e a quantidade de arestas
	scanf("%d %d", &c, &v);

	// leio o grafo
	for(int i=1; i<=v; i++){

	int c1, c2, g;
	scanf("%d %d %d", &c1, &c2, &g);

	lista[c1].PB(ii(c2,g));
	lista[c2].PB(ii(c1,g));
	}

	// imprimo a menor distância par de 1 a C
	printf("%d\n", dijkstra(1,c));

	return 0;
	}

view raw

mania.cpp

hosted with ❤ by GitHub