#include<iostream>
#include<algorithm>
#include<vector>
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
int n, m;
int a, b;
long long int L, t;
long long int ans;
vector< pair< int, long long int > > E[100002];
long long int A[100002], T;
int color, x;
long long int maxi, mini;
int vis[100002];
void lejano( int node, long long int d ){
if( d > maxi ){
maxi = d;
x = node;
}
vis[node] = color;
for( int i = 0; i < E[node].size(); i++ )
if( vis[ E[node][i].first ] != color )
lejano( E[node][i].first, d + E[node][i].second );
}
long long int dist[100002];
void DFS( int node, long long int d, int c ){
if( c ){
dist[node] = max( dist[node], d );
maxi = max( maxi, dist[node] );
mini = mini == -1 ? dist[node] : min( mini, dist[node] );
} else {
dist[node] = d;
}
vis[node] = color;
for( int i = 0; i < E[node].size(); i++ )
if( vis[ E[node][i].first ] != color )
DFS( E[node][i].first, d + E[node][i].second, c );
}
long long int checkTree( int r ){
int a, b;
color++; maxi = -1; x = 0;
lejano( r, 0 );
a = x;
color++; maxi = -1; x = 0;
lejano( a, 0 );
b = x;
maxi = -1; mini = -1;
color++;
DFS( a, 0, 0 );
color++;
DFS( b, 0, 1 );
ans = max( ans, maxi );
return mini;
}
int main(){
optimizar_io
cin >> n >> m >> L;
for( int i = 1; i <= m; i++ ){
cin >> a >> b >> t;
E[a].push_back( make_pair( b, t ) );
E[b].push_back( make_pair( a, t ) );
}
for( int i = 0; i < n; i++ )
if( !vis[i] )
A[++T] = checkTree( i );
sort( A + 1, A + T + 1 );
reverse( A + 1, A + T + 1 );
if( T > 1 ){
ans = max( ans, A[1] + A[2] + L );
if( T > 2 )
ans = max( ans, A[2] + A[3] + 2 * L );
}
cout << ans << "\n";
return 0;
}
Compilation message
dreaming.cpp: In function 'void lejano(int, long long int)':
dreaming.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for( int i = 0; i < E[node].size(); i++ )
| ~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void DFS(int, long long int, int)':
dreaming.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for( int i = 0; i < E[node].size(); i++ )
| ~~^~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccUPeALX.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc6ylSuU.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc6ylSuU.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
