#include "bits/stdc++.h"
#include "dreaming.h"
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=1e5;
vector<pair<int,int>> adj[N];
int dp[N],dp2[N];
bool done[N];
vector<int> cc;
void getCC(int u,int e) {
cc.push_back(u);
for (auto &[v,len]: adj[u]) if (v!=e) {
getCC(v,u);
}
}
void dfs(int u,int e) {
for (auto &[v,len]: adj[u]) if (v!=e) {
dfs(v,u);
cmax(dp[u],dp[v]+len);
}
}
void dfs2(int u,int e) {
multiset<int> lengths;
lengths.insert(dp2[u]);
for (auto &[v,len]: adj[u]) if (v!=e) {
lengths.insert(dp[v]+len);
}
for (auto &[v,len]: adj[u]) if (v!=e) {
lengths.erase(lengths.find(dp[v]+len));
assert(!lengths.empty());
dp2[v]=*lengths.rbegin()+len;
dfs2(v,u);
lengths.insert(dp[v]+len);
}
}
int travelTime(int n, int m, int k, int u[], int v[], int len[]) {
for (int i=0;i<m;i++) {
adj[u[i]].emplace_back(v[i],len[i]);
adj[v[i]].emplace_back(u[i],len[i]);
}
vector<int> diams;
const int inf = 1e9;
for (int i=0;i<n;i++) {
if (!done[i]) {
cc.clear();
getCC(i,-1);
for (int &j: cc) {
assert(!done[j]);
done[j]=true;
}
dfs(i,-1);
dfs2(i,-1);
int rs=inf;
for (int &j: cc) {
cmin(rs,max(dp[j],dp2[j]));
}
diams.push_back(rs);
// dp[u] = max dist in subtree of u,
// dp2[u] = max dist in everything except subtree of u
}
}
sort(diams.begin(),diams.end());
n = int(diams.size());
if (diams.size()==1) {
return diams[0];
} else if (diams.size()==2) {
return diams[0]+diams[1]+k;
} else {
return max(diams[n-1]+diams[n-2]+k,diams[n-2]+diams[n-3]+2*k);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,k; cin >> n >> m >> k;
int u[m],v[m],len[m];
for (int i=0;i<m;i++) {
cin >> u[i] >> v[i] >> len[i];
}
cout << travelTime(n,m,k,u,v,len) << "\n";
}
Compilation message
/usr/bin/ld: /tmp/cc5wjtMr.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchan6Kq.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
