Seletiva IOI 2014

trafego.cpp

// Ivan Carvalho
// Tráfego - Seletiva IOI - OBI 2014
#include <bits/stdc++.h>
#define MAXN 50010
using namespace std;
typedef pair<int,int> ii;
struct aresta{
	int alvo,d,g,r;
};
int N,M;
vector<aresta> grafo[MAXN];
int processado[MAXN];
int main(){
	scanf("%d %d",&N,&M);
	for(int i=1;i<=M;i++){
		int u;
		aresta davez;
		scanf("%d %d %d %d %d",&u,&davez.alvo,&davez.d,&davez.g,&davez.r);
		grafo[u].push_back(davez);
	}
	priority_queue<ii, vector<ii> ,greater<ii> > Dijkstra;
	Dijkstra.push(MP(0,1));
	while(!Dijkstra.empty()){
		ii davez = Dijkstra.top();
		Dijkstra.pop();
		int dist = davez.first, v = davez.second;
		if(v == N){
			printf("%d\n",dist);
			return 0;
		}
		if(processado[v]) continue;
		processado[v] = 1;
		for(int i = 0;i<grafo[v].size();i++){
			int u = grafo[v][i].alvo, d = grafo[v][i].d, g = grafo[v][i].g, r = grafo[v][i].r;
			int instante = dist + d;
			if(instante % (g+r) >= g){
				instante = instante - (instante % (g+r)) + g + r;
			}
			Dijkstra.push(MP(instante,u));
		}
	}
	printf("-1\n");
	return 0;
}