You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
52 lines
1.4 KiB
C++
52 lines
1.4 KiB
C++
#include <cstdio>
|
|
#include <cstring>
|
|
template <typename T>
|
|
inline T max(T a, T b) { return a > b ? a : b; }
|
|
template <typename T>
|
|
inline T min(T a, T b) { return a < b ? a : b; }
|
|
int head[200005], next[200005 << 2], to[200005 << 2], len[200005 << 2], ecnt, n, m, que[200005 << 1];
|
|
long long disa[200005], disb[200005];
|
|
inline void addEdge(int f, int t, int l)
|
|
{
|
|
ecnt++;
|
|
next[ecnt] = head[f];
|
|
head[f] = ecnt;
|
|
to[ecnt] = t;
|
|
len[ecnt] = l;
|
|
}
|
|
int bfs(int s, long long *dis)
|
|
{
|
|
int h = 0, t = 0;
|
|
dis[s] = 0;
|
|
que[t++] = s;
|
|
for (int x; h != t; h++)
|
|
for (int cur = head[x = que[h]]; cur; cur = next[cur])
|
|
if (dis[to[cur]] == -1)
|
|
dis[que[t++] = to[cur]] = dis[x] + len[cur];
|
|
int id = -1;
|
|
long long val = -1;
|
|
for (int i = 1; i <= n; i++)
|
|
if (dis[i] > val) val = dis[id = i];
|
|
return id;
|
|
}
|
|
int main()
|
|
{
|
|
scanf("%d%d", &n, &m);
|
|
for (int i = 0, x, y, z; i < m; i++)
|
|
{
|
|
scanf("%d%d%d", &x, &y, &z);
|
|
addEdge(x, y, z);
|
|
addEdge(y, x, z);
|
|
}
|
|
memset(disa, -1, sizeof(disa));
|
|
memset(disb, -1, sizeof(disb));
|
|
int a = bfs(1, disa);
|
|
memset(disa, -1, sizeof(disa));
|
|
int b = bfs(a, disa);
|
|
bfs(b, disb);
|
|
long long ans = 0;
|
|
for (int i = 1; i <= n; i++) ans = max(ans, min(disa[i], disb[i]));
|
|
ans += disb[a];
|
|
printf("%lld", ans);
|
|
return 0;
|
|
} |