#include " dreaming.h"
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;
int dis1[100010],dis2[100010];
bool visited[100010];
vector<pair<int,int> > v[100010],pb,pbb;
vector<int> pa,nl,len,len2;
queue<int> q;
pair<int,int> tmp;
int a[100010],b[100010],c[100010];
bool shd;
void dfs(pair<int,int> n){
visited[n.first]=true;
nl.push_back(n.first);
if(dis2[n.first]==n.second){
pbb.push_back(n);
double targ=n.second/2.0;
double dd=targ;
int pu;
for(int i=0;i<nl.size();i++){
double diff=abs((double)dis2[nl[i]]-targ);
if(diff<=dd){
dd=diff;
pu=max(dis2[nl[i]],n.second-dis2[nl[i]]);
}
}
if(!shd){
len.push_back(pu);
shd=true;
tmp=n;
}
else if(pu<len.back()){
len.pop_back();
len.push_back(pu);
tmp=n;
}
}
for(int i=0;i<v[n.first].size();i++){
if(!visited[v[n.first][i].first]){
dis2[v[n.first][i].first]=dis2[n.first]+v[n.first][i].second;
dfs(make_pair(v[n.first][i].first,n.second));
}
}
nl.pop_back();
// dis2[n.first]=0;
}
void dfs2(pair<int,int> n){
visited[n.first]=true;
nl.push_back(n.first);
if(dis2[n.first]==n.second){
pbb.push_back(n);
double targ=n.second/2.0;
double dd=targ;
int pu;
for(int i=0;i<nl.size();i++){
double diff=abs((double)dis2[nl[i]]-targ);
if(diff<=dd){
dd=diff;
pu=max(dis2[nl[i]],n.second-dis2[nl[i]]);
}
}
if(!shd){
len2.push_back(pu);
shd=true;
tmp=n;
}
else if(pu<len2.back()){
len2.pop_back();
len2.push_back(pu);
tmp=n;
}
}
for(int i=0;i<v[n.first].size();i++){
if(!visited[v[n.first][i].first]){
dis2[v[n.first][i].first]=dis2[n.first]+v[n.first][i].second;
dfs(make_pair(v[n.first][i].first,n.second));
}
}
nl.pop_back();
// dis2[n.first]=0;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]){
for(int i=0;i<n;i++){
dis1[i]=-1;
}
for(int i=0;i<m;i++){
v[a[i]].push_back(make_pair(b[i],t[i]));
v[b[i]].push_back(make_pair(a[i],t[i]));
}
for(int i=0;i<n;i++){
if(dis1[i]==-1){
dis1[i]=0;
q.push(i);
visited[i]=true;
int mxd=0,nd=i;
while(!q.empty()){
int cur=q.front();
if(dis1[cur]>mxd){
mxd=dis1[cur];
nd=cur;
}
q.pop();
for(int i=0;i<v[cur].size();i++){
if(!visited[v[cur][i].first]){
q.push(v[cur][i].first);
dis1[v[cur][i].first]=dis1[cur]+v[cur][i].second;
visited[v[cur][i].first]=true;
}
}
}
pa.push_back(nd);
}
}
for(int i=0;i<n;i++){
dis1[i]=-1;
visited[i]=false;
}
for(int i=0;i<pa.size();i++){
dis1[pa[i]]=0;
q.push(pa[i]);
visited[pa[i]]=true;
int mxd=0,nd=i;
while(!q.empty()){
int cur=q.front();
if(dis1[cur]>mxd){
mxd=dis1[cur];
nd=cur;
}
q.pop();
for(int i=0;i<v[cur].size();i++){
if(!visited[v[cur][i].first]){
q.push(v[cur][i].first);
dis1[v[cur][i].first]=dis1[cur]+v[cur][i].second;
visited[v[cur][i].first]=true;
}
}
}
pb.push_back(make_pair(nd,mxd));
}
for(int i=0;i<n;i++){
dis2[i]=-1;
visited[i]=false;
}
for(int i=0;i<pb.size();i++){
dis2[pb[i].first]=0;
shd=false;
dfs(pb[i]);
}
for(int i=0;i<n;i++){
dis2[i]=-1;
visited[i]=false;
}
for(int i=0;i<pbb.size();i++){
dis2[pb[i].first]=0;
shd=false;
dfs2(pbb[i]);
}
for(int i=0;i<len.size();i++){
len[i]=min(len[i],len2[i]);
}
sort(len.begin(),len.end());
int ml=-1;
for(int i=0;i<n;i++){
if(dis2[i]>ml){
ml=dis2[i];
}
}
int yo=n-m;
int ans=-1;
if(yo>=3){
ans=max(len[yo-1]+len[yo-2]+l,len[yo-3]+len[yo-2]+2*l);
}
else if(yo==2){
ans=len[yo-1]+len[yo-2]+l;
}
ans=max(ans,ml);
// printf("%lld\n",yo);
return ans;
}
Compilation message
dreaming.cpp:1:10: fatal error: dreaming.h: No such file or directory
1 | #include " dreaming.h"
| ^~~~~~~~~~~~~
compilation terminated.
