← 返回题目列表

AtCoder · awc0073_e

E. 除雪机路线

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

分数: 466 分

问题陈述

高桥负责规划该市的除雪行动。该市有 N 交叉路口,编号自 1 to N。交叉点通过以下方式连接 M 道路,每条道路均可双向通行。可能有多条道路连接同一对顶点,但它们被视为不同的道路。的 i第条路连接路口 U_i 和交叉路口 V_i,并且需要 W_i 分钟,扫雪机沿任一方向穿过该区域。

高桥必须规划一条从交叉路口的车库出发的除雪车路线 1,遍历每个 M 道路至少一次,最后在路口返回车厂 1。一旦一条道路朝任一方向行驶,就被认为没有积雪;没有必要在两个方向上遍历它。除雪机可能会多次穿越同一条道路,无论方向相同还是相反。也允许通过交叉路口 路线期间 1 任意次数。由于燃料有限,高桥希望在尽可能短的时间内完成巡逻。

求除雪机离开路口所需的最短总行驶时间(以分钟为单位) 1,每条路至少遍历一次,并返回路口 1.

保证给定的图是连通的。

约束

  • 2 \leq N \leq 10^5
  • N - 1 \leq M \leq 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^6
  • 该图已连接
  • 奇数度的顶点数最多为 16。这里,顶点的度是指入射到该顶点的边的数量,其中多边边的每条边都单独计数
  • 可能有多条道路连接同一对顶点(可能存在多条边)
  • 所有输入值均为整数

输入

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 第一行包含 N,交叉点的数量,以及 M,道路数量,以空格分隔。
  • 以下 M 行提供有关每条道路的信息。
  • 的 树的 (1 + i)第行包含两个交叉点 U_i, V_i 由 i第条路,以及时间 遍历它所需的 W_i (以分钟为单位),以空格分隔。

输出

以单行输出除雪机至少穿越每条道路一次并返回交叉路口所需的最小总行程时间(整数) 1.


示例输入 1

3 3
1 2 4
2 3 5
3 1 6

示例输出 1

15

示例输入 2

3 2
1 2 3
2 3 5

示例输出 2

16

示例输入 3

8 11
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 7 6
7 8 7
8 1 8
1 3 2
2 5 3
4 7 1

示例输出 3

48

示例输入 4

15 20
1 2 10
2 3 8
3 4 7
4 5 12
5 6 3
6 7 9
7 8 5
8 9 11
9 10 6
10 11 4
11 12 8
12 13 7
13 14 13
14 15 2
15 1 14
1 8 20
3 10 15
5 12 6
7 14 9
2 9 18

示例输出 4

228

示例输入 5

2 1
1 2 1000000

示例输出 5

2000000