#P13733. [ARC078F] Mole and Abandoned Mine

    ID: 12935 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-状压 DP子掩码递推 (s-1)&mask补集转化

[ARC078F] Mole and Abandoned Mine

题目描述

鼹鼠决定住在一个废弃矿井中,该矿井可以表示为一个包含编号为 11 到 NN 的 NN 个顶点和 MM 条边的简单连通无向图。第 ii 条边连接顶点 aia_i 和 bib_i,移除这条边需要 cic_i 日元。

鼹鼠希望通过移除一些边,使得从顶点 11 到顶点 NN 的路径仅有一条,并且在路径上不经过同一个顶点两次。请计算实现这一目标所需的最小资金。

输入格式

输入以以下格式从标准输入中给出。

NN MM
a1a_1 b1b_1 c1c_1
⋮\vdots
aMa_M bMb_M cMc_M

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100

输出 #1

200

输入输出样例 #2

输入 #2

2 1
1 2 1

输出 #2

0

输入输出样例 #3

输入 #3

15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491

输出 #3

133677

说明/提示

限制条件

  • 2≤N≤152 \leq N \leq 15
  • N−1≤M≤N(N−1)/2N-1 \leq M \leq N(N-1)/2
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 1≤ci≤1061 \leq c_i \leq 10^6
  • 给定的图中不存在重边或自环
  • 给定的图是连通图

样例解释 1

在下图中,用红色虚线表示被移除的边。按照该图的方式移除两条边,总共需要 200200 日元。

样例解释 2

有时从一开始,顶点 11 到顶点 NN 的路径就只有一种。