| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 742044 | angels | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}