#include "dreaming.h" #include "bits/stdc++.h" using namespace std; const int N = 100001; const int INF = INT_MAX; vector<pair<int,int>>G[N]; void add(int u,int v,int w) { G[u].push_back({v,w}); G[v].push_back({u,w}); } bool vis[N]; vector<int>all; void dfs(int v) { all.push_back(v); vis[v]=1; for(pair<int,int> nxt : G[v]) { int u=nxt.first; if(!vis[u]) dfs(u); } } int dis[N]; pair<int,int>get(int v) { for(int u : all) dis[u]=INF; queue<int>q; q.push(v); dis[v]=0; while(!q.empty()) { int node=q.front(); q.pop(); for(pair<int,int> nxt : G[node]) { int u=nxt.first; int w=nxt.second; if(dis[node]+w<dis[u]) { dis[u]=dis[node]+w; q.push(u); } } } pair<int,int>res={-INF,-INF}; for(int u : all) res=max(res,{dis[u] , v}); return res; } pair<int,int> find_center() { vector<pair<int,int>>srt; for(int v : all) srt.push_back(get(v)); sort(srt.begin(),srt.end()); return {srt[0].second , srt[0].first}; } int travelTime(int N , int M , int L , int A[] , int B[] , int T[]) { for(int i = 0;i < M;i++) add(A[i] , B[i] , T[i]); vector < pair < int , int > > srt; for(int i = 0;i < N;i++) { if(vis[i]) continue; all.clear(); dfs(i); pair < int , int > cw = find_center(); int center = cw.first; int max_w = cw.second; srt.push_back({max_w , center}); } sort(srt.rbegin() , srt.rend()); for(int i = 1;i < srt.size();i++) add(srt[0].second , srt[i].second , L); all.clear(); for(int i = 0;i < N;i++) all.push_back(i); int res = -INF; for(int i = 0;i < N;i++) res = max(res , get(i).first); return res; }