#include "dreaming.h" #include<bits/stdc++.h> using namespace std; vector<pair<int,int>> v[100010]; int visited[100010]; int dp[100010]; int sumi1[100010]; int node1[100010]; int sumi2[100010]; priority_queue<int> pq; void dfs(int u,int pa){ for(auto g:v[u]){ if(g.first!=pa){ dfs(g.first,u); if(g.second+sumi1[g.first]>sumi1[u]){ sumi2[u]=sumi1[u]; sumi1[u]=g.second+sumi1[g.first]; node1[u]=g.first; } else if(g.second+sumi1[g.first]>sumi2[u]){ sumi2[u]=g.second+sumi1[g.first]; } } } visited[u]=1; } void dfs2(int u,int pa,int root,int q){ dp[root]=min(dp[root],max(q,sumi1[u])); for(auto g:v[u]){ if(g.first!=pa){ if(g.first!=node1[u]){ dfs2(g.first,u,root,max(q,sumi1[u])+g.second); } else{ dfs2(g.first,u,root,max(q,sumi2[u])+g.second); } } } } int travelTime(int n, int m, int l, int a[], int b[], int t[]) { for(int i=0;i<m;i++){ v[a[i]].push_back({b[i],t[i]}); v[b[i]].push_back({a[i],t[i]}); } int co=0; for(int i=0;i<n;i++){ if(visited[i]==1) continue; co++; dfs(i,-1); dp[i]=INT_MAX; dfs2(i,-1,i,0); pq.push(dp[i]); } if(co==1) return 0; if(co==2){ int xxx=pq.top(); pq.pop(); int yyy=pq.top(); return(xxx+yyy+l); } int xxx=pq.top(); pq.pop(); int yyy=pq.top(); pq.pop(); int zzz=pq.top(); return(max(xxx+l+yyy,yyy+zzz+2*l)); }