#include "dreaming.h" using namespace std; #include <iostream> #include <vector> #include <algorithm> long long maxjos[100005]; long long max2jos[100005]; long long canjos[100005]; vector<int>vec; vector<pair<int,int> >adj[100005]; int dist[100005][5]; int fre[100005]; void dfs(int curr,int par) { vec.push_back(curr); for(auto k:adj[curr]) { if(k.first!=par) { fre[k.first]=1; dfs(k.first,curr); } } } void updatedist(int curr,int par,int iter) { for(auto k:adj[curr]) { if(k.first!=par) { dist[k.first][iter]=dist[curr][iter]+k.second; updatedist(k.first,curr,iter); } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for(int i=0; i<M; i++) { adj[A[i]].push_back({B[i],T[i]}); adj[B[i]].push_back({A[i],T[i]}); } int n=N; vector<int>ans; for(int i=0; i<n; i++) { if(fre[i]==0) { vec.clear(); fre[i]=1; dfs(i,-1); updatedist(i,-1,0); int maxim=vec[0],maxim2=vec[0]; for(auto k:vec) { if(dist[k][0]>=dist[maxim][0]) { maxim=k; } } updatedist(maxim,-1,1); for(auto k:vec) { if(dist[k][1]>=dist[maxim2][1]) { maxim2=k; } } updatedist(maxim2,-1,2); int rez=1000000006; for(auto k:vec) { rez=min(rez,max(dist[k][2],dist[k][1])); } ans.push_back(rez); } } sort(ans.begin(),ans.end()); reverse(ans.begin(),ans.end()); int sol=ans[0]; if(ans.size()>=2) { sol=max(sol,ans[0]+ans[1]+L); } if(ans.size()>=3) { sol=max(sol,ans[2]+ans[1]+2*L); } return sol; }