#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
int n, m, L, r1, r2;
int D[100010];
bool vis[100010];
vector<pair<int,int> > adj[100010];
void dfs1(int p, int u) {
vis[u] = 1;
for(auto& it : adj[u])
if(it.first != p) {
dfs1(u, it.first);
D[u] = max(D[u], D[it.first] + it.second);
}
}
void dfs2(int p, int u, int E) {
r1 = min(r1, max(D[u], E));
int mx[2] = {-1,-1}, idx[2]={-1,-1};
for(auto& it : adj[u])
if(it.first != p) {
int val = D[it.first] + it.second;
if(val > mx[0]) mx[1] = mx[0], idx[1] = idx[0], mx[0] = val, idx[0] = it.first;
else if(val > mx[1]) mx[1] = val, idx[1] = it.first;
}
r2 = max(r2, D[u]);
if(mx[0]!=-1&&mx[1]!=-1) r2 = max(r2, mx[0] + mx[1]);
for(auto& it : adj[u]) {
if(it.first == p) continue;
if(idx[0] != it.first) dfs2(u, it.first, it.second + max(E, mx[0]));
else dfs2(u, it.first, it.second + max(E, mx[1]));
}
}
int main() {
scanf("%d%d%d", &n, &m, &L);
for(int i=0; i<m; i++) {
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
adj[u].push_back({v,c});
adj[v].push_back({u,c});
}
vector<int> va;
int res = 0;
for(int i=0; i<n; i++) {
if(vis[i]) continue;
r1 = 1e9; r2 = 0;
dfs1(i,i);
dfs2(i,i,0);
va.push_back(r1);
res = max(res, r2);
}
sort(all(va));
if(sz(va)>=2) res = max(res, va[sz(va)-2] + va.back() + L);
if(sz(va)>=3) res = max(res, va[sz(va)-3] + va[sz(va)-2] + 2 * L);
printf("%d", res);
return 0;
}
Compilation message
dreaming.cpp: In function 'int main()':
dreaming.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
37 | scanf("%d%d%d", &n, &m, &L);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
40 | scanf("%d%d%d",&u,&v,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~
/tmp/ccn8Rv2Y.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccS1SEuo.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccS1SEuo.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
