#include <bits/stdc++.h>
//#include "dreaming.h"
#define MAXN 100005
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define max3(a,b,c) max(max(a,b),c)
using namespace std;
//declarations
int N , M , L;
int radio1, radio2 ;
int d[MAXN] , dX[MAXN];
bool marc[MAXN] ;
vector<int> radios ;
vector<pii> adj[MAXN] ;
//utilities
void atribution()
{ lp(i,0,N) dX[i] = d[i] ; }
void ini(int x)
{ memset(d , -1 , sizeof d) ; d[x] = 0 ;}
void dfs(int x)
{
marc[x] = 1 ;
lp(i , 0 , adj[x].size() )
{
int v = adj[x][i].ff ;
if(d[v] != -1) continue ;
d[v] = d[x] + adj[x][i].ss ;
dfs(v) ;
}
}
int findMax()
{ return max_element(d, d+N) - d ; }
int findRadio(int X , int Y)
{
int ans = d[X] ;
lp(i,0,N)
{
if(d[i] == -1) continue ;
int a = d[i] , b = dX[i] ;
a = max(a,b) ;
ans = min(ans , a) ;
}
return ans ;
}
int travelTime( int n , int m , int l , int A[] , int B[] , int T[] )
{
N = n , M = m , L = l;
int ans = -1 ;
vector<int> edge ;
lp(i,0,M)
{
int a = A[i] , b = B[i] ;
adj[a].pb( pii(b, T[i]) ) ;
adj[b].pb( pii(a, T[i]) ) ;
edge.pb(T[i]) ;
}
if(M < N-2)
{
sort(edge.begin() , edge.end()) ;
reverse(edge.begin() , edge.end()) ;
lp(i,0,M) ans = max(ans , edge[i]) ;
if(M <= 3)
lp(i,0,3) edge.pb(0) ;
ans = max( ans , edge[0] + edge[1] + L ) ;
ans = max( ans , edge[1] + edge[2] + 2*L ) ;
return ans ;
}
lp(i,0,N)
if(!marc[i])
{
ini(i) ; dfs(i) ;
int X = findMax() ;
ini(X) ; dfs(X) ;
atribution() ;
int Y = findMax() ;
ini(Y) ; dfs(Y) ;
int k = findRadio(X,Y) ;
radios.pb(k) ;
ans = max(ans, d[X]) ;
//printf("%d %d %d\n", X, Y, k) ;
}
sort(radios.begin() , radios.end()) ;
reverse(radios.begin() , radios.end() ) ;
ans = max( ans , radios[0] + radios[1] + L ) ;
if(radios.size() == 2) return ans ;
ans = max( ans , radios[1] + radios[2] + 2*L ) ;
return ans ;
}
int main()
{
int n , m , l , a[MAXN] , b[MAXN] , t[MAXN] ;
scanf("%d %d %d", &n, &m, &l) ;
lp(i,0,m) scanf("%d%d%d", &a[i] , &b[i] , &t[i]) ;
printf("%d\n",travelTime(n,m,l,a,b,t)) ;
}
Compilation message
dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:5:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define lp(i,a,b) for(int i = a ; i < b ; i++)
dreaming.cpp:37:8:
lp(i , 0 , adj[x].size() )
~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:37:5: note: in expansion of macro 'lp'
lp(i , 0 , adj[x].size() )
^~
dreaming.cpp: In function 'int main()':
dreaming.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &m, &l) ;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:122:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
lp(i,0,m) scanf("%d%d%d", &a[i] , &b[i] , &t[i]) ;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/tmp/cc7aLSQt.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccLTIRGl.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccLTIRGl.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
