#include <bits/stdc++.h>
using namespace std;
#define num long long
#define next first
#define cost second
#define t_road pair<int, num>
#define t_roads vector<t_road>
#define graph vector<t_roads>
#define ndata vector<num>
graph roads;
// here, max is refered as the first maximal
// mix is refered as the second maximal
ndata max_dist;
ndata visit_id; num stage = 0;
num computeDistance (int node, int parent, num cst) {
max_dist[node] = cst;
visit_id[node] = stage;
for (t_road road : roads[node]) {
if (road.next == parent) continue ;
max_dist[node] = max(
max_dist[node],
computeDistance(road.next, node, cst + road.cost)
);
}
max_dist[node] -= cst;
return max_dist[node] + cst;
}
num excentricity (int node, int parent, num incoming) {
num local = max(incoming, max_dist[node]);
assert(local >= 0);
visit_id[node] = stage;
num max = 0;
num mix = 0;
for (t_road road : roads[node]) {
if (road.next == parent) continue ;
num next_d = road.cost + max_dist[road.next];
if (next_d > max) {
mix = max;
max = next_d;
} else if (next_d > mix) mix = next_d;
}
for (t_road road : roads[node]) {
if (road.next == parent) continue ;
num next_i = max == max_dist[road.next] + road.cost ? mix : max;
if (next_i < incoming) next_i = incoming;
local = min(local, excentricity(road.next, node, road.cost + next_i));
}
return local;
}
num travelTime(int N, int M, int L, int A[], int B[], int T[]) {
roads.resize(N);
visit_id.resize(N, -1);
max_dist.resize(N);
for (int i = 0; i < M; i ++) {
roads[A[i]].push_back({ B[i], T[i] });
roads[B[i]].push_back({ A[i], T[i] });
assert(T[i] >= 0);
}
for (int i = 0; i < N; i ++)
if (visit_id[i] != stage)
computeDistance(i, -1, 0);
stage ++;
vector<num> values;
for (int i = 0; i < N; i ++)
if (visit_id[i] != stage)
values.push_back(excentricity(i, -1, 0));
sort(values.rbegin(), values.rend());
if (values.size() == 1) return values[0];
if (values.size() == 2) return L + values[0] + values[1];
return L + values[1] + max(values[0], values[2] + L);
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, L;
cin >> N >> M >> L;
int A[100000];
int B[100000];
int T[100000];
for (int i = 0; i < M; i ++)
cin >> A[i] >> B[i] >> T[i];
cout << travelTime(N, M, L, A, B, T);
}
Compilation message
/usr/bin/ld: /tmp/ccKEoBjc.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccgcN5ta.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccgcN5ta.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
