#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 degree[MAXN] ;
int d[MAXN] ;
bool marc[MAXN] ;
vector<int> radios ;
vector<pii> adj[MAXN] ;
//utilities
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 diam = *max_element(d,d+N) ;
int ans = diam ;
lp(i,0,N)
ans = min( ans , max(d[i] , diam - d[i]) ) ;
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 ;
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]) ) ;
degree[a] ++ ;
degree[b] ++ ;
}
lp(i,0,N)
if(degree[i] == 1 and !marc[i])
{
ini(i) ; dfs(i) ;
int V = findMax() ;
ini(V) ; dfs(V) ;
int k = findRadio(V) ;
radios.pb(k) ;
ans = max(ans , 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:35:8:
lp(i , 0 , adj[x].size() )
~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:35:5: note: in expansion of macro 'lp'
lp(i , 0 , adj[x].size() )
^~
dreaming.cpp: In function 'int main()':
dreaming.cpp:98: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:99: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/ccvpcnCJ.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccof9Gki.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccof9Gki.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
