LYDSY 1509
题目大意
暂无
题目解法
暂无
RTFC
#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;
}