#include <bits/stdc++.h>
//#include "dreaming.h"
#define X first
#define Y second
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int MN = 100010;
const int INF = 2 * 1e9 + 10;
int n, m, l;
int min_max[MN], c[MN];
int nxt[MN], maxp[MN], h[MN], nxte[MN];
bool mark[MN], bio[MN];
vector<pii> g[MN], v;
vector<int> used;
set<int> s;
bool comp(pii a, pii b){
return a.Y > b.Y;
}
int Find(int x){
//cout << x << " +\n";
if(h[x] == x)
return x;
return h[x] = Find(h[x]);
}
void Union(int x, int y){
h[x] = Find(y);
}
void use(int x){
if(!mark[x]){
used.pb(x);
mark[x] = true;
}
}
int maxPath(int x){
use(x);
bio[x] = true;
maxp[x] = 0;
int mi = x;
for(pair<int, int> e : g[x]){
int y = e.X;
if(bio[y])
continue;
int val = e.Y;
int f = maxPath(y);
if(maxp[y] + val > maxp[x]){
maxp[x] = maxp[y] + val;
mi = f;
nxt[x] = y;
nxte[x] = val;
}
}
//cout << x << " " << maxp[x] << " " << mi << "\n";
return mi;
}
void clearUsed(){
for(int x : used){
nxt[x] = 0;
maxp[x] = 0;
mark[x] = false;
bio[x] = 0;
nxte[x] = 0;
}
used.clear();
}
pii findCenter(int x, bool printp){
clearUsed();
x = maxPath(x);
clearUsed();
int y = maxPath(x);
int s = maxp[x];
int zb = 0;
if(printp){
return {s, 0};
}
int mn = INF, mni = x;
while(x != y){
if(mn > max(zb, s - zb)){
mn = max(zb, s - zb);
mni = x;
}
//cout << x << " -> " << nxt[x] << " (" << nxte[x] << " " << zb << ")\n";
zb += nxte[x];
x = nxt[x];
}
if(mn == INF)
mn = 0;
return {mni, mn};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
ios_base::sync_with_stdio(false);
for(int i = 0; i < MN; i++){
h[i] = i;
c[i] = i;
}
//cin >> n >> m >> l;
n = N;
m = M;
l = L;
for(int i = 0; i < n; i++)
s.insert(i);
for(int i = 0; i < m; i++){
int a, b, t;
//cin >> a >> b >> t;
a = A[i];
b = B[i];
t = T[i];
g[a].push_back({b, t});
g[b].push_back({a, t});
a = Find(a);
b = Find(b);
s.erase(a);
s.erase(b);
Union(a, b);
s.insert(Find(a));
}
auto it = s.begin();
while(it != s.end()){
pii res = findCenter(*it, 0);
c[*it] = res.X;
min_max[*it] = res.Y;
v.pb(res);
it++;
}
sort(v.begin(), v.end(), comp);
int ret = v[0].Y;
if(v.size() > 1)
ret = max(ret, v[0].Y + v[1].Y + l);
if(v.size() > 2)
ret = max(ret, v[1].Y + v[2].Y + l * 2);
return ret;
}
int main(){
int n, m, l;
int a[MN], b[MN], t[MN];
cin >> n >> m >> l;
for(int i = 0; i < m; i++)
cin >> a[i] >> b[i] >> t[i];
cout << travelTime(n, m, l, a, b, t) << "\n";
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc3INytD.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccVEPZVy.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVEPZVy.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
