Solução Infomática Avançado - Semana 38

Para resolvermos esse problema vamos fazer uma modificação no Dijkstra. Partindo do um vértice $v$ com distância atual $d_v$ , vamos considerar os filhos $u$ , que tem uma distância $d_u$ já calculada, e são ligados por uma aresta de peso $w$ .

No algoritmo vamos considerar dois casos:

Caso $d_u > d_v + w$ : Então vale a pena colocar essa aresta, e gravamos que o menor caminho chegando na aresta $u$ , parte de $v$
Caso $d_u = d_v + w$ : Então existe outro menor caminho chegando em $u$ , agora por $x$ . Podemos adicionar num vetor que o menor caminho chegando na aresta $u$ também parte de $v$

Após processarmos esse Dijkstra fazemos uma DFS, partindo do vértice final, que passa pelos vértices que formam o menor caminho chegando no vértice atual (partindo do vértice de onde começamos o Dijkstra). Essa vetor de adjacência foi calculado do Dijkstra acima.

Agora para todo vértice temos as arestas proíbidas, ou seja, que fazem parte de algum menor caminho chegando no vértice de destino. Uma maneira fácil de remover essas arestas é dar sort em ambos os vetores de adjacência, e usar set_difference para gravar no vetor de adjcência original os caminhos que somente aparecem em um dos vetores.

Com o vetor de adjacência sem arestas que fazem parte do menor caminho já computado, podemos rodar o Dikjstra novamente e assim teremos a distância partindo do vértice inicial para o vétice final.

Código para melhor entendimento:

	#include <bits/stdc++.h>

	#define ff first
	#define ss second

	using namespace std;

	typedef pair<int, int> ii;

	const int inf = 0x3f3f3f3f;
	const int maxn = 510;

	vector<ii> v[maxn];
	vector<ii> mir[maxn];
	vector<ii> inv[maxn];

	int d[maxn];
	int vis[maxn];

	void dijkstra(int ini)
	{
	memset(d, 0x3f, maxn*4);
	d[ini] = 0;

	for (int i = 0; i < maxn; i++) mir[i].clear();

	priority_queue<ii, vector<ii>, greater<ii> > pq;

	pq.push({0, ini});

	while (!pq.empty()) {

	int w, at;
	tie(w, at) = pq.top();
	pq.pop();

	if (w > d[at]) continue;

	for (ii uu : v[at]) {

	int u = uu.ff, ww = uu.ss;

	if (d[u] == w + ww) {

	mir[u].push_back({at, ww});
	}
	else if (d[u] > w + ww) {

	mir[u].clear();
	d[u] = w + ww;
	mir[u].push_back({at, ww});

	pq.push({d[u], u});
	}
	}
	}
	}

	void dfs(int x)
	{
	vis[x] = 1;

	for (ii uu : mir[x]) {

	int u = uu.ff, w = uu.ss;

	inv[u].push_back({x, w});

	if (vis[u]) continue;

	dfs(u);
	}
	}

	int main()
	{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	while (true) {

	int n, m;
	cin >> n >> m;

	if (n == 0 and m == 0) break;

	for (int i = 0; i < n; i++) {

	mir[i].clear();
	inv[i].clear();
	v[i].clear();
	vis[i] = 0;
	}

	int ini, fim;
	cin >> ini >> fim;

	for (int i = 0; i < m; i++) {

	int a, b, w;
	cin >> a >> b >> w;

	v[a].push_back({b, w});
	}

	dijkstra(ini);

	dfs(fim);

	for (int i = 0; i < n; i++) {

	sort(v[i].begin(), v[i].end());
	sort(inv[i].begin(), inv[i].end());

	vector<ii> r;

	set_difference(v[i].begin(), v[i].end(), inv[i].begin(), inv[i].end(),
	back_inserter(r));

	v[i] = r;
	}

	dijkstra(ini);

	if (d[fim] == inf) cout << -1 << "\n";
	else cout << d[fim] << "\n";
	}
	}

view raw

quase_menor.cpp

hosted with ❤ by GitHub