← 返回题目列表

AtCoder · arc165_c

C. 图上的社交距离

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个简单的连通无向图 N 顶点编号 1 to N。该图有 M 加权边,以及 i第一条边连接顶点 A_i 和 B_i 重量为 W_i。另外,令连接两个顶点的简单路径的权重为简单路径中包含的边的权重之和。

让我们将每个顶点绘制为红色或蓝色。求整数的最大值 X 其着色满足以下条件:

  • 对于连接用相同颜色绘制的两个不同顶点的每条简单路径,该简单路径的权重至少为 X.
什么是简单路径? 图表中的 对于顶点 无向图中的 X 和 Y 在图表中 G,一系列顶点 v_1,v_2, \ldots, v_k 这样 v_1=X, v_k=Y,和 v_i 和 v_{i+1} 由每个边缘连接 1\leq i\leq k-1 被称为 步行 从顶点 X 到顶点 Y。 此外,如果 v_1,v_2, \ldots, v_k 都是不同的,走路叫a 简单路径 (或只是 路径).

约束

  • 3 \leq N \leq 2 \times 10^5
  • N-1 \leq M \leq \min(\frac{N(N-1)}{2},2 \times 10^5)
  • 1 \leq A_i < B_i \leq N
  • 1 \leq W_i \leq 10^9
  • 给定的图是一个简单的连通无向图。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1 W_1
A_2 B_2 W_2
\vdots
A_M B_M W_M

输出

打印答案。


示例输入 1

3 3
1 2 5
2 3 6
1 3 12

示例输出 1

11

考虑是否存在满足条件的着色 X=11。如果我们绘制顶点 1 和 3 红色和顶点 2 蓝色,简单路径 1-2-3 连接相同颜色的顶点的权重为 5+6=11。这是连接相同颜色顶点的简单路径的最小权重,因此这种颜色满足条件。

可以证明没有着色满足条件 X=12 或以上。因此,答案是 11.


示例输入 2

10 20
7 10 982219000
3 10 968366179
2 4 992330437
5 6 984414664
2 8 897295423
7 9 155604979
6 8 958833005
2 3 973209957
3 7 985173062
6 10 963895817
2 10 986243534
4 5 721724794
1 3 657562445
1 6 566370694
1 4 988050146
1 9 967817807
4 9 796531581
5 9 983960054
1 10 964450079
8 9 959369491

示例输出 2

952136560

示例输入 3

10 20
5 6 871895994
8 10 873709822
3 5 454175869
6 10 980782191
2 6 901290987
1 8 298092290
4 8 693116157
4 5 947939338
7 8 934395075
7 9 759563833
5 8 779870031
4 6 919637355
2 9 822858749
4 10 855497285
3 7 954942051
1 2 950411658
4 7 665939990
3 4 634533617
5 7 908372507
1 9 591466693

示例输出 3

759563833