Tráfico

trafico.cpp

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