#include<bits/stdc++.h>
#include "dreaming.h"
#define MAXN 100007
using namespace std;
const int inf=1e9;
int n,m,len;
vector< pair<int,int> > v[MAXN];
bool vis[MAXN];
int down[MAXN],up[MAXN],mindist,maxdist;
vector<int> w;
void dfs(int x,int p){
vis[x]=true;
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p)continue;
dfs(v[x][i].first,x);
down[x]=max(down[x],down[v[x][i].first]+v[x][i].second);
}
}
void dfs2(int x,int p){
vis[x]=true;
multiset<int> s;
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p)continue;
s.insert(down[v[x][i].first]+v[x][i].second);
}
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p)continue;
s.erase(s.find(down[v[x][i].first]+v[x][i].second));
up[v[x][i].first]=up[x];
if(!s.empty())up[v[x][i].first]=max(up[v[x][i].first], *s.rbegin());
up[v[x][i].first]+=v[x][i].second;
dfs2(v[x][i].first,x);
s.insert(down[v[x][i].first]+v[x][i].second);
}
mindist=min(mindist,max(down[x],up[x]));
maxdist=max(maxdist,max(down[x],up[x]));
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
//int travelTime(int N, int M, int L, vector<int> A, vector<int> B, vector<int> T) {
n=N; m=M; len=L;
for(int i=1;i<=m;i++){
A[i-1]++; B[i-1]++;
v[A[i-1]].push_back({B[i-1],T[i-1]});
v[B[i-1]].push_back({A[i-1],T[i-1]});
}
for(int i=1;i<=n;i++){
if(!vis[i])dfs(i,0);
}
for(int i=1;i<=n;i++)vis[i]=false;
for(int i=1;i<=n;i++){
if(!vis[i]){
mindist=inf; dfs2(i,0);
w.push_back(mindist);
}
}
sort(w.begin(),w.end());
reverse(w.begin(),w.end());
if(w.size==1)return maxdist;
if(w.size()==2){
return max(maxdist,w[0]+w[1]+len);
}else{
return 1/0;
return max(max(maxdist,w[0]+w[1]+len),w[1]+w[2]+2*len);
}
}
/*int main(){
cout<<travelTime(12,8,2,{0,8,2,5,5,1,1,10},{8,2,7,11,1,3,9,6},{4,2,4,3,7,1,5,3})<<"\n";
return 0;
}*/
Compilation message
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
dreaming.cpp:35:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:79:7: error: invalid use of member function 'std::vector<_Tp, _Alloc>::size_type std::vector<_Tp, _Alloc>::size() const [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int]' (did you forget the '()' ?)
79 | if(w.size==1)return maxdist;
| ~~^~~~
| ()
dreaming.cpp:84:11: warning: division by zero [-Wdiv-by-zero]
84 | return 1/0;
| ~^~
