Solução Avançado Informática - Semana 41

Solução de Frederico Bulhões

É possível ver que esse problema é um problema de menor caminho em grafo com um limite a mais: que o dano no casco não ultrapasse o limite.

Podemos ainda usar o algoritmo de Dijkstra, porém o vetor de distância necessita de uma dimensão a mais. Em vez de $dist[i]$ conter a menor distância da fonte ao vértice $i$ , nós em vez disso definimos $dist[i][j]$ como a menor distância partindo da fonte para o vértice $i$ enquanto sustentando exatamente $j$ de dano no casco.

Pensando nisso devemos alterar o algoritmo de Dijkstra. Normalmente após tirarmos um vértice da priority_queue, passaríamos por todos os vértices adjacentes. Para essa questão vamos considerar todos os vértices adjacentes, e também todos os possíveis valores de dano ao casco.

Podemos então passar por todos os valores possíveis de dano menores que $k$ , e ver a menor distância para o vértice $B$ .

Código para melhor entendimento:

	// solucao de Lúcio Cardoso

	#include <bits/stdc++.h>

	using namespace std;

	const int MAXN = 2010;
	const int MAXK = 210;
	const int INF = 1e9+10;

	typedef pair<int, int>pii;

	int k, n, m, dist[MAXN][MAXK];
	vector< pair<int, pii> > grafo[MAXN];
	bool mark[MAXN];

	void Dijkstra(int S, int x)
	{
	for (int i = 1; i <= n; i++) dist[i][x] = INF;
	dist[S][x] = 0;
	priority_queue< pii, vector<pii>, greater<pii> > fila;
	fila.push(make_pair(0, S));

	int davez = -1;
	while (!fila.empty())
	{
	int atual = fila.top().second;
	fila.pop();
	if (!mark[atual])
	davez = atual, mark[atual] = 1;
	if (davez == -1) continue;

	for (int i = 0; i < grafo[davez].size(); i++)
	{
	int v = grafo[davez][i].second.first, d = grafo[davez][i].first;
	int hull = grafo[davez][i].second.second;

	if (hull >= x) continue;

	if (dist[v][x] > dist[davez][x-hull]+d)
	{
	dist[v][x] = dist[davez][x-hull]+d;
	fila.push(make_pair(dist[v][x], v));
	}
	}
	}
	}

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

	cin >> k >> n >> m;

	while (m--)
	{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	grafo[a].push_back(make_pair(c, make_pair(b, d)));
	grafo[b].push_back(make_pair(c, make_pair(a, d)));
	}
	int x, y;
	cin >> x >> y;

	for (int i = 0; i <= k; i++)
	{
	memset(mark, 0, sizeof mark);
	Dijkstra(x, i);
	}

	if (dist[y][k] == INF)
	cout << "-1\n";
	else
	cout << dist[y][k] << "\n";
	}

view raw

convex_hull.cpp

hosted with ❤ by GitHub