#include<bits/stdc++.h>
using namespace std;
const int INF=1987654321;
int n, m, l, cnt, ch[100010], M[2][100010], D[100010], A[100010];
struct C{
int r, l;
bool operator<(const C &a)const{
return a.r>r;
}
}data[100010];
vector<pair<int, int> > v[100010];
void dfs(int x){
ch[x]=1;
for(int i=0; i<v[x].size(); i++){
int u=v[x][i].first;
if(ch[u]==0){
dfs(u);
if(M[0][x]<v[x][i].second+M[0][u]){
M[1][x]=M[0][x];
M[0][x]=v[x][i].second+M[0][u];
}
else if(M[1][x]<v[x][i].second+M[0][u]){
M[1][x]=M[0][u]+v[x][i].second;
}
D[x]=max(D[x], D[u]);
}
}
D[x]=max(D[x], M[0][x]+M[1][x]);
}
void dfs1(int x, int len, int y, int inx){
ch[x]=0;
if(M[0][x]+len==D[y]){
if(abs(M[0][x]-len)<data[inx].r-data[inx].l){
data[inx].r=max(M[0][x], len);
data[inx].l=min(M[0][x], len);
}
}
if(M[0][x]+M[1][x]==D[y]){
if(abs(M[0][x]-M[1][x])<data[inx].r-data[inx].l){
data[inx].r=max(M[0][x], M[1][x]);
data[inx].l=min(M[0][x], M[1][x]);
}
}
for(int i=0; i<v[x].size(); i++){
int u=v[x][i].first;
if(ch[u]==1){
if(v[x][i].second+M[0][u]==M[0][x]) dfs1(u, max(len+v[x][i].second, M[1][x]+v[x][i].second), y, inx);
else dfs1(u, max(len+v[x][i].second, M[0][x]+v[x][i].second), y, inx);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
n=N, m=M, l=L;
for(int i=0; i<m; i++){
int a=A[i], b=B[i], c=T[i];
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
for(int i=0; i<n; i++){
if(ch[i]==0){
dfs(i);
A[cnt++]=i;
}
}
for(int i=0; i<cnt; i++){
data[i].r=INF;
data[i].l=0;
dfs1(A[i], 0, A[i], i);
}
sort(data, data+cnt);
if(cnt==1) return data[0].r+data[0].l;
else if(cnt==2) return max(data[0].r+data[0].l, max(data[1].r+data[1].l, data[0].r+data[1].r+l));
else{
int ans=0;
for(int i=0; i<cnt; i++) ans=max(ans, data[i].r+data[i].l);
return max(ans, max(data[cnt-1].r+data[cnt-2].r+l, data[cnt-2].r+data[cnt-3].r+l+l));
}
}
Compilation message
dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v[x].size(); i++){
~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, int, int, int)':
dreaming.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v[x].size(); i++){
~^~~~~~~~~~~~
/tmp/cc18uFXD.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
