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

Solução de Frederico Bulhões

Esse problema é um menor caminho em um grafo porém com uma condição a mais: somente podemos avançar de um sinal quando ele estiver verde.

Então para resolver esse problema vamos considerar um menor caminho de Dijkstra, porém quando consideramos colocar uma aresta e ela está vermelha, consideramos apenas o memento imediato quando ela se torna verde novamente.

A partir daí vemos quato tempo leva para partir de um vértice A e chgar num B.

Código para melhor entendimento:


// solucao de Frederico Bulhoes
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ii, ii> pii;
const int maxn = 60000;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector<pii> v[maxn];
// peso, destino, verde, vermelho
ll peso[maxn];
void dijkstra()
{
for (int i = 1; i <= n; i++) peso[i] = inf;
priority_queue<ii, vector<ii>, greater<ii> > pq;
peso[1] = 0;
pq.push(ii(0ll,1ll));
while (!pq.empty()) {
ll atual = pq.top().ss;
ll w = pq.top().ff;
pq.pop();
if (w > peso[atual]) continue;
for (int i = 0; i < v[atual].size(); i++) {
pii u = v[atual][i];
ll tempo = u.ff.ff;
ll u2 = u.ff.ss;
ll vermelho = u.ss.ff;
ll verde = vermelho + u.ss.ss;
ll t = w + tempo;
if (t%verde >= vermelho) t = (t/verde+1)*verde;
if (peso[u2] > t) {
peso[u2] = t;
pq.push(ii(t, u2));
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
ll a, b, d, g, r;
cin >> a >> b >> d >> g >> r;
v[a].push_back(pii(ii(d, b), ii(g, r)));
}
dijkstra();
if (peso[n] == inf) cout << -1 << "\n";
else cout << peso[n] << "\n";
return 0;
}

view raw

trafico.cpp

hosted with ❤ by GitHub