1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 50;
int n, m, tot = 1, head[maxn], ver[maxn], edge[maxn], nxt[maxn];
ll d[maxn], a[maxn], b[maxn];
void add(int x, int y, int z) {
ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void bfs(int st, ll d[]) {
queue<int> q;
memset(d, -1, sizeof(ll) * maxn);
d[st] = 0, q.push(st);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i];
if (~d[y]) continue;
d[y] = d[x] + edge[i];
q.push(y);
}
}
}
int get_mx(ll d[]) {
int ed = 1;
for (int i = 1; i <= n; ++i) {
if (d[ed] < d[i]) ed = i;
}
return ed;
}
int main() {
cin >> n >> m;
for (int x, y, z, i = 1; i <= m; ++i) {
cin >> x >> y >> z;
add(x, y, z), add(y, x, z);
}
bfs(1, d);
int p = get_mx(d);
bfs(p, d);
int q = get_mx(d);
ll ans = d[q];
bfs(p, a), bfs(q, b);
ll tmp, dis = 0;
for (int i = 1; i <= n; ++i) {
tmp = min(a[i], b[i]);
if (tmp > dis) {
dis = tmp;
}
}
cout << ans + dis << endl;
return 0;
}
|