#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MM = 100010;
vector<pii> adj[MM];
bool vis[MM];
int dis[MM];
vector<int> diam;
int furthest = 0, cit = -1;
void dfs(int src, int cost, int prev){
if(cost > furthest){
furthest = cost;
cit = src;
}
if(dis[src] < cost){
dis[src] = cost;
}
vis[src] = true;
for(pii i: adj[src]){
if(i.first != prev){
dfs(i.first, cost+i.second, src);
}
}
}
int ans = 100000000;
void dfs2(int src, int prev, int c){
ans = min(ans, dis[src]);
for(pii u: adj[src]){
if(u.first!=prev){
dfs2(u.first, src, u.second + c);
}
}
}
int radius(int src){
dfs(src, 0, -1);
int i = cit;
cit = -1; furthest = 0;
dfs(i,0, -1);
int gg = cit;
cit = -1; furthest = 0;
dfs(gg,0,-1);
diam.push_back(furthest);
dfs2(gg, -1, 0);
int ss = ans;
ans = 100000000;
cit = -1; furthest = 0;
return ss;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for(int i=0; i < M; i++){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
vector<int> radii;
for(int i=0; i < N; i++){
if(!vis[i]){
radii.push_back(radius(i));
}
}
int ans = 0;
sort(radii.begin(), radii.end());
reverse(radii.begin(), radii.end());
if(radii.size() >= 2){
ans = max(ans, radii[0]+radii[1]+L);
}
if(radii.size() >= 3){
ans = max(ans, radii[1]+radii[2]+L+L);
}
for(int i: diam){
ans = max(ans, i);
}
return ans;
}
int a[MM], b[MM], c[MM];
int main(){
int n, m, l;
cin >> n >> m >> l;
for(int i=0; i < m; i++){
int x, y, z; cin >> x >> y >> z;
a[i] = x; b[i] = y; c[i] = z;
}
cout << travelTime(n, m, l, a, b, c) << '\n';
return 0;
}
Compilation message
/tmp/cciViyF1.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccvhnp6g.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccvhnp6g.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
