← 返回题目列表

AtCoder · awc0022_e

E. 送货司机路线

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

分数: 433 分

问题陈述

有 N 某个地区的城镇,编号为 1 to N。有些城镇有道路相连,所有道路都是双向的,并且有 M 道路总数。的 i第条路连接城镇 U_i 和镇 V_i,沿着这条路行驶所需的时间是 W_i。请注意,不一定所有城镇都可以通过道路到达。

高桥是一名送货司机。他必须从位于城镇的配送中心出发 1,将包裹递送至所有 N 城镇,然后返回城镇配送中心 1。具体来说,他从城镇出发 1,通过道路反复从一个城镇移动到另一个城镇,每个城镇至少访问一次,最后返回城镇 1。他被允许多次访问同一个城镇并多次经过同一条道路。

找出沿该路线经过的道路的最短总行驶时间。如果多次穿越同一条道路,则每次穿越时都会添加其行驶时间。如果不存在有效路由,则输出 -1.

约束

  • 2 \leq N \leq 15
  • 1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i (无自环)
  • If i \neq j,那么 \{U_i, V_i\} \neq \{U_j, V_j\} (任意一对城镇之间至多有一条道路)
  • 1 \leq W_i \leq 10^6
  • 所有输入值均为整数

输入

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 第一行包含城镇数量 N 和道路数量 M,用空格分隔。
  • 以下 M 行每条都包含有关道路的信息。的 i- 第这些行包含两个城镇的号码 U_i, V_i 由 i第 条路,以及行车时间 那条路的 W_i ,以空格分隔。

输出

单行输出高桥至少访问每个城镇一次并返回城镇所需的最短总行程时间 1。如果不存在有效路由,则输出 -1.


示例输入 1

4 4
1 2 10
2 3 15
3 4 20
4 1 25

示例输出 1

70

示例输入 2

4 2
1 2 5
3 4 8

示例输出 2

-1

示例输入 3

6 7
1 2 3
1 3 10
2 3 4
2 4 7
3 5 2
4 6 5
5 6 6

示例输出 3

30