Caminhos Mínimos.cpp

#include<bits/stdc++.h>
#define int long long
#define tii tuple<int, int, int>
#define pii pair<int, int>
using namespace std;
const int maxn = 1e4 + 5, INF = 1e9;

vector<pii> adj[maxn];
vector<int> dist_bfs;
int n;

vector<int> bfs(){
	queue<int> q;
	bool mark[maxn] = {};
	vector<int> dist(n+1);
	q.push(1), mark[1] = true;
	while(q.size()){
		int u = q.front();
		q.pop();
		for(auto [w, v] : adj[u]) if(!mark[v]){
			mark[v] = true, dist[v] = dist[u] + 1;
			q.push(v);
		}
	}

	return dist;
}

bool solve(int k){
	bool mark[maxn] = {};
	int dist[maxn] = {}, dist1[maxn] = {};
	priority_queue<tii, vector<tii>, greater<tii>> q;

	q.push({0, 0, 1});
	while(q.size()){
		auto [d, qtd, u] = q.top();
		q.pop();
		if(mark[u]) continue;
		mark[u] = true;
		dist[u] = d;
		dist1[u] = qtd;

		for(auto[w, v] : adj[u]) if(!mark[v]){
			q.push({dist[u]+w+k, qtd+1, v});
		}
	}

	for(int i = 1; i <= n; i++) if(dist1[i]!=dist_bfs[i]) return false;
	return true;
}

int32_t main(){
	int m; cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({c, b});
		adj[b].push_back({c, a});
	}

	dist_bfs = bfs();

	int l=0, r=2*INF, ans = 2*INF;
	while(l<=r){
		int mid = (l+r)>>1;
		if(solve(mid)) r = mid-1, ans = mid;
		else l = mid+1;
	}

	cout << ans << '\n';
}