#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int MAX = 1e5 + 10;
int ans;
vector <pair <int, int>> adj[MAX];
pair <int, int> ma[MAX][2];
bool visited[MAX];
template <typename T>
void upd(T *ma, T x, int n) {
for(int i = 0; i < n; i++) {
if(ma[i] < x) {
swap(ma[i], x);
}
}
}
void dfs(int u) {
for(auto [v, w] : adj[u]) {
if(visited[v] == true) {
continue;
}
visited[v] = true;
dfs(v);
upd(ma[u], make_pair(ma[v][0].first + w, v), 2);
}
ans = max(ans, ma[u][0].first + ma[u][1].first);
}
int dfs2(int u, int pw) {
int res = max(ma[u][0].first, pw);
for(auto [v, w] : adj[u]) {
if(visited[v] == true) {
continue;
}
visited[v] = true;
int nw = pw;
if(ma[u][0].second == v) {
nw = max(nw, ma[u][1].first);
}
else {
nw = max(nw, ma[u][0].first);
}
res = min(res, dfs2(v, nw + w));
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++) {
A[i]++, B[i]++;
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
for(int i = 1; i <= N; i++) {
ma[i][0] = make_pair(0, -1);
ma[i][1] = make_pair(0, -1);
}
for(int i = 1; i <= N; i++) {
if(visited[i] == false) {
visited[i] = true;
dfs(i);
}
}
for(int i = 1; i <= N; i++) {
visited[i] = false;
}
vector <int> max_dist;
for(int i = 1; i <= N; i++) {
if(visited[i] == false) {
visited[i] = true;
max_dist.push_back(dfs2(i, 0));
}
}
sort(max_dist.rbegin(), max_dist.rend());
if(max_dist.size() > 1) {
ans = max(ans, max_dist[0] + max_dist[1] + L);
}
if(max_dist.size() > 2) {
ans = max(ans, max_dist[1] + max_dist[2] + 2 * L);
}
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M, L;
cin >> N >> M >> L;
int A[M], B[M], T[M];
for(int i = 0; i < M; i++) {
cin >> A[i] >> B[i] >> T[i];
}
cout << travelTime(N, M, L, A, B, T);
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccBI3Nny.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccc5QGqA.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
