#include "dreaming.h" #include "bits/stdc++.h" using namespace std; const int N = 100001; const int INF = INT_MAX; int n; vector<pair<int,int>>G[N]; map<pair<int,int>,int>dsc; void add(int u,int v,int w) { dsc[{u,v}]=w; dsc[{v,u}]=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] , u}); return res; } vector<int> get_path(int u,int v) { for(int u : all) dis[u]=INF; queue<int>q; q.push(u); dis[u]=0; while(!q.empty()) { int node=q.front(); q.pop(); for(pair<int,int> nxt : G[node]) { int u=nxt.first; if(dis[node]+1<dis[u]) { dis[u]=dis[node]+1; q.push(u); } } } vector<int>res; int cur_node=v; while(1) { res.push_back(v); if(v==u) break; int mn=INF; for(pair<int,int> node : G[v]) mn=min(mn,dis[node.first]); for(pair<int,int> node : G[v]) { if(dis[node.first]==mn) { v=node.first; break; } } } return res; } pair<int,int> find_center() { pair<int,int>mx1=get(all[0]); pair<int,int>mx2=get(mx1.second); int u=mx1.second; int v=mx2.second; int tot=mx2.first; int cur=0; vector<int>path=get_path(u,v); if(path.size()==1) { return {path[0],0}; } vector<pair<int,int>>srt; for(int i=1;i<path.size();i++) { int wg=dsc[{path[i-1],path[i]}]; cur+=wg; tot-=wg; srt.push_back({max(cur,tot),path[i]}); } sort(srt.begin(),srt.end()); return {srt[0].second,srt[0].first}; } pair<int,int> get_mx(int v) { vector<int>d(n,INF); queue<int>q; d[v]=0; q.push(v); 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(d[node]+w<d[u]) { d[u]=d[node]+w; q.push(u); } } } pair<int,int>res; for(int i=0;i<n;i++) res=max(res,{d[i],i}); return res; } int get_dia() { pair<int,int>mx1=get_mx(0); pair<int,int>mx2=get_mx(mx1.second); return mx2.first; } int travelTime(int N , int M , int L , int A[] , int B[] , int T[]) { n = N; 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); return get_dia(); }