#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int maxN = 1e5 + 5;
long long dist[2][maxN], visited[maxN];
vector<pair<long long, long long> > adj[maxN];
vector<int> component;
multiset<pair<long long, long long > > comps;
pair<long long, int> dfs(int node, int parent, long long cur_dist, long long *store, bool need_add){
visited[node] = 1;
if (need_add) component.push_back(node);
else store[node] = cur_dist;
pair<long long, int> ans = make_pair(cur_dist, node);
for (pair<int, int> child: adj[node]){
if (child.first == parent) continue;
ans = max(ans, dfs(child.first, node, cur_dist+child.second, store, need_add));
}
return ans;
}
int main(){
long long n, m, L;
cin >> n >> m >> L;
for (int i = 0; i < m; i++){
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back(make_pair(b, c));
adj[b].push_back(make_pair(a, c));
}
cout << endl;
for (int i = 0; i < n; i++){
if (visited[i]) continue;
component.clear();
pair<long long, int> furthest = dfs(i, -1, 0, dist[0], true);
pair<long long, int> next_furthest = dfs(furthest.second, -1, 0, dist[0], false);
dfs(next_furthest.second, -1, 0, dist[1], false);
long long mini_max = 1e18;
for (int node: component) mini_max = min(mini_max, max(dist[0][node], dist[1][node]));
comps.insert(make_pair(mini_max, next_furthest.first));
}
while(comps.size() > 1){
pair<long long, long long> first = *comps.begin();
pair<long long, long long> second = *comps.rbegin();
comps.erase(comps.begin());
comps.erase(--comps.end());
pair<long long, long long> new_comp;
new_comp.first = min(max(first.first, second.first + L), max(second.first, first.first + L));
new_comp.second = max(first.second, max(second.second, first.first + second.first + L));
comps.insert(new_comp);
}
pair<long long, long long> ans = *comps.begin();
cout << ans.second << endl;
}
Compilation message
/usr/bin/ld: /tmp/ccz938UN.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc1fGWHN.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc1fGWHN.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
