Seletiva IOI 2017

caminhos.cpp

// Ivan Carvalho
// Caminhos- Seletiva IOI - OBI 2017
#include <bits/stdc++.h>
#define MT make_tuple
using namespace std;
typedef long long ll;
typedef tuple<ll,ll,ll> trinca;
typedef pair<ll,ll> ii;
const int MAXN = 2*1e4;
vector<ii> grafo[MAXN];
int processado[MAXN],qtd[MAXN],n,m;
int func(ll delta){
	memset(processado,0,sizeof(processado));
	priority_queue<trinca, vector<trinca>, greater<trinca> > Dijsktra;
	Dijsktra.push(MT(0,0,1));
	while(!Dijsktra.empty()){
		trinca davez = Dijsktra.top();
		Dijsktra.pop();
		ll dist = get<0>(davez),percorrido = get<1>(davez),v = get<2>(davez);
		if(processado[v]) continue;
		if(percorrido != qtd[v]) return 0;
		processado[v] = 1;
		for(int i = 0;i<grafo[v].size();i++){
			ll u = grafo[v][i].first, peso = grafo[v][i].second;
			if(processado[u]) continue;
			Dijsktra.push(MT( dist + peso + delta,percorrido + 1,u ));
		}
	}
	return 1;
}
int main(){
	cin.tie(0);ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1;i<=m;i++){
		ll u,v,w;
		cin >> u >> v >> w;
		grafo[u].push_back(ii(v,w));
		grafo[v].push_back(ii(u,w));
	}
	queue<ii> bfs;
	bfs.push(ii(0,1));
	processado[1] = 1;
	while(!bfs.empty()){
		ii davez = bfs.front();
		bfs.pop();
		ll dist = davez.first, v = davez.second;
		qtd[v] = dist;
		for(int i = 0;i<grafo[v].size();i++){
			ll u = grafo[v][i].first;
			if(!processado[u]){
				processado[u] = 1;
				bfs.push(ii(dist+1,u));
			}
		}
	}
	ll ini = 0, fim = 1e9 + 1e8, meio,resp = -1;
	while(ini <= fim){
		meio = (ini+fim)/2;
		if(func(meio)){
			resp = meio;
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}
	cout << resp << endl;
	return 0;
}