#include <bits/stdc++.h> #include "dreaming.h" #define Big_INT long long Big_INT maxdist1[100010]; Big_INT maxdist2[100010]; Big_INT maxdist3[100010]; std::vector<std::vector<std::pair<Big_INT,Big_INT>>> adj; std::vector<Big_INT> currentNum; void bfs(Big_INT start){ std::queue<std::pair<Big_INT,Big_INT>> q; q.push({start,0}); maxdist1[start]=0; while(!q.empty()){ Big_INT curr = q.front().first; currentNum.push_back(curr); Big_INT currw = q.front().second; q.pop(); for(auto [to,w]:adj[curr]){ if(maxdist1[to]==-1){ maxdist1[to]=currw+w; q.push({to,currw+w}); } } } } void bfs2(Big_INT start){ std::queue<std::pair<Big_INT,Big_INT>> q; q.push({start,0}); maxdist2[start]=0; while(!q.empty()){ Big_INT curr = q.front().first; //currentNum.push_back(curr); Big_INT currw = q.front().second; q.pop(); for(auto [to,w]:adj[curr]){ if(maxdist2[to]==-1){ maxdist2[to]=currw+w; q.push({to,currw+w}); } } } } void bfs3(Big_INT start){ std::queue<std::pair<Big_INT,Big_INT>> q; q.push({start,0}); maxdist3[start]=0; while(!q.empty()){ Big_INT curr = q.front().first; //currentNum.push_back(curr); Big_INT currw = q.front().second; q.pop(); for(auto [to,w]:adj[curr]){ if(maxdist3[to]==-1){ maxdist3[to]=currw+w; q.push({to,currw+w}); } } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { adj.resize(N+5); for(Big_INT i=0;i<M;i++){ adj[A[i]].push_back({B[i],T[i]}); adj[B[i]].push_back({A[i],T[i]}); } for(Big_INT i=0;i<N;i++){ maxdist1[i]=-1; maxdist2[i]=-1; maxdist3[i]=-1; } std::vector<Big_INT> value; Big_INT maxincomvalue=0; for(Big_INT i=0;i<N;i++){ if(maxdist1[i]==-1){ bfs(i); Big_INT nodeA=i,distA=0; for(auto vNode:currentNum){ if(maxdist1[vNode]>distA){ nodeA=vNode; distA=maxdist1[vNode]; } } bfs2(nodeA); Big_INT nodeB=nodeA,distB=0; for(auto vNode:currentNum){ if(maxdist2[vNode]>distB){ nodeB=vNode; distB=maxdist2[vNode]; } } bfs3(nodeB); Big_INT minmax=1e18; Big_INT nnn=1e18; for(auto vNode:currentNum){ minmax=std::min(minmax,std::max(maxdist2[vNode],maxdist3[vNode])); nnn=std::min(minmax,(maxdist2[vNode]+maxdist3[vNode])); } maxincomvalue=std::max(maxincomvalue,nnn); currentNum.resize(0); value.push_back(minmax); } } std::sort(value.begin(),value.end()); Big_INT max=value.back(); if(value.size()>=2)max+=value[value.size()-2]+L; if(value.size()>=3)max=std::max(max,value[value.size()-2]+value[value.size()-3]+2*L); max=std::max(maxincomvalue,max); // if(value.size()>=2){ // max=std::max(max,); // } return max; }