#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX = 100005;
const int INF = (int)1e9;
vector<pii> graph[MAX];
int dist[MAX], par[MAX];
int diam, pos1, pos2;
bool vst1[MAX], vst2[MAX];
void dfs1(int u, int cur)
{
vst1[u] = true;
dist[u] = cur;
if (diam < cur)
{
diam = cur;
pos1 = u;
}
for (auto t : graph[u])
{
int v = t.first;
if (!vst1[v])
dfs1(v, cur + t.second);
}
}
void dfs2(int u, int cur)
{
vst2[u] = true;
dist[u] = cur;
if (diam < cur)
{
diam = cur;
pos2 = u;
}
for (auto t : graph[u])
{
int v = t.first;
if (!vst2[v])
{
par[v] = u;
dfs2(v, cur + t.second);
}
}
}
int main(void)
{
int n, m, l, i;
scanf("%d %d %d", &n, &m, &l);
while (m--)
{
int u, v, t;
scanf("%d %d %d", &u, &v, &t);
++u, ++v;
graph[u].emplace_back(v, t);
graph[v].emplace_back(u, t);
}
int ans = 0;
vector<pii> res;
for (i = 1; i <= n; i++)
if (!vst1[i])
{
pos1 = pos2 = i;
diam = 0;
dfs1(i, 0);
diam = 0;
par[pos1] = 0;
dfs2(pos1, 0);
res.emplace_back(pos2, diam);
ans = max(ans, diam);
}
vector<int> rad;
for (auto t : res)
{
int p = t.first;
int r = INF; // radius
while (p)
{
r = min(r, max(dist[p], t.second - dist[p]));
p = par[p];
}
rad.push_back(r);
}
sort(rad.rbegin(), rad.rend());
if (rad.size() >= 2)
ans = max(ans, rad[0] + rad[1] + l);
if (rad.size() >= 3)
ans = max(ans, rad[1] + rad[2] + l * 2);
printf("%d\n", ans);
return 0;
}
Compilation message
dreaming.cpp: In function 'int main()':
dreaming.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
60 | scanf("%d %d %d", &n, &m, &l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
65 | scanf("%d %d %d", &u, &v, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/tmp/ccApjIrv.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccPy1LjO.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccPy1LjO.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
