AT_arc165_c.[ARC165C] Social Distance on Graph

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 $N$ 个顶点的简单连通无向图，顶点编号为 $1$ 到 $N$ 。图中有 $M$ 条带权无向边，第 $i$ 条边连接顶点 $A_i$ 和 $B_i$ ，权值为 $W_i$ 。对于连接两个顶点的简单路径，其权值定义为路径上所有边权的总和。

现在要对每个顶点染成红色或蓝色。请你求出满足以下条件的整数 $X$ 的最大值：

对于任意两个染成相同颜色的不同顶点，它们之间的任意一条简单路径的权值都不少于 $X$ 。

简单路径的定义如下：对于图 $G$ 上的顶点 $X,Y$ ，顶点序列 $v_1,v_2,\ldots,v_k$ ，满足 $v_1=X$ ， $v_k=Y$ ，且对于 $1\leq i\leq k-1$ ， $v_i$ 和 $v_{i+1}$ 之间有边连接，这样的序列称为从 $X$ 到 $Y$ 的步行。如果 $v_1,v_2,\ldots,v_k$ 均互不相同，则称为从 $X$ 到 $Y$ 的简单路径（或简称路径）。

输入格式

输入按以下格式从标准输入读入。

$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
```

输入#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

说明/提示

限制条件

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

样例解释 1

考虑 $X=11$ 时是否存在满足条件的染色方法。将顶点 $1,3$ 染为红色，顶点 $2$ 染为蓝色时，连接同色顶点的简单路径 $1-2-3$ 的权值为 $5+6=11$ 。这是所有同色顶点间简单路径权值的最小值，因此这种染色方法满足条件。当 $X\geq 12$ 时，不存在满足条件的染色方法。因此答案为 $11$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页