#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
#define pb push_back
#define popb pop_back
#define all(v) (v).begin(),(v).end()
#define ff first
#define ss second
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
// SOLUTION \\
const int MAX_N = 1e5 + 4;
int n, m, l;
vpi adj[MAX_N];
vi p, rnk;
vi wt;
vi comps;
vpi cost[MAX_N];
int parent[MAX_N];
bitset<MAX_N> visited;
int d[MAX_N];
int findset(int x){ return p[x]== x? x: findset(p[x]);}
void unite(int i, int j)
{
int x= findset(i);
int y = findset(j);
if(x == y)
return ;
if(rnk[x] > rnk[y])
swap(x,y);
if(rnk[x] == rnk[y])
rnk[y]++;
p[x] = y;
return ;
}
void solve()
{
cin >> n >> m >> l;
p.assign(n,0); rnk.assign(n,0);
wt.assign(n,0);
int maxt = 0;
for(int i= 0; i <n; i ++)
p[i]= i ;
for(int i= 1; i <= m; i ++)
{
int a, b, w;
cin >> a >> b >> w;
adj[a].pb({b,w});
adj[b].pb({a,w});
unite(a,b);
}
for(int i = 0; i <n; i ++)
{
int x= findset(i);
if(visited[x])
continue;
visited[x] = 1;
unordered_set<int> seen;
set<pii> s;
s.insert({0,x});
seen.insert(x);
int ed = x;
while(!s.empty())
{
pii u = *(s.begin());
s.erase(s.begin());
int node = u.ss;
int dis = u.ff;
for(auto e: adj[node])
{
if(seen.count(e.ff) != 0)
continue;
seen.insert(e.ff);
s.insert({dis+e.ss,e.ff});
}
if(s.empty())
ed = node;
}
int lgest = 0;
s.clear(); seen.clear();
s.insert({0,ed});
int cent = x;
seen.insert(ed);
int mint = MOD;
while(!s.empty())
{
pii u = *(s.begin());
s.erase(s.begin());
int node = u.ss;
int dis = u.ff;
for(auto e: adj[node])
{
if(seen.count(e.ff) != 0)
continue;
seen.insert(e.ff);
s.insert({dis + e.ss,e.ff});
}
if(s.empty())
lgest = dis;
}
s.clear(); seen.clear();
s.insert({0,ed});
seen.insert(ed);
parent[ed]= -1;
int st = x;
while(!s.empty())
{
pii u = *(s.begin());
s.erase(s.begin());
int node = u.ss;
int dis = u.ff;
d[node] = dis;
for(auto e: adj[node])
{
if(seen.count(e.ff) != 0)
continue;
seen.insert(e.ff);
parent[e.ff] = node;
s.insert({dis + e.ss,e.ff});
}
if(dis == lgest)
{
st = node;
break;
}
}
int u = st;
maxt = max(maxt,lgest);
while(u != -1)
{
int cst = max(d[u],lgest-d[u]);
if(cst < mint)
{
mint = cst;
cent = u;
}
u = parent[u];
}
comps.pb(mint);
}
sort(all(comps));
reverse(all(comps));
if(m <= n-3)
maxt = max(maxt,comps[1]+comps[2]+l+l);
if(m <= n-2)
maxt = max(maxt,comps[0]+comps[1]+l);
cout << maxt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt = 1;
while(tt--)
{
solve();
}
}
Compilation message
dreaming.cpp:22:1: warning: multi-line comment [-Wcomment]
22 | // SOLUTION \\
| ^
dreaming.cpp: In function 'void solve()':
dreaming.cpp:95:13: warning: variable 'cent' set but not used [-Wunused-but-set-variable]
95 | int cent = x;
| ^~~~
/usr/bin/ld: /tmp/cct9YIR3.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccfeUWS3.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccfeUWS3.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
