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"; | |
| } |
