分数: 500 点
问题陈述
有一个加权简单有向图 N 顶点和 M 边缘。 顶点已编号 1 to N,以及 i第一条边的权重为 W_i 并从顶点延伸 U_i 到顶点 V_i。 权重可以为负,但图表不包含负循环。
确定是否存在至少访问每个顶点一次的游走。如果存在这样的步行,则找到所遍历的边的最小总权重。 如果多次遍历同一条边,则每次遍历都会添加该边的权重。
这里,“访问每个顶点至少一次的遍历”是顶点序列 v_1,v_2,\dots,v_k 满足以下两个条件:
- 对于每个 i (1\leq i\leq k-1),有一条从顶点延伸的边 v_i 到顶点 v_{i+1}.
- 对于每个 j\ (1\leq j\leq N),有 i (1\leq i\leq k) 这样 v_i=j.
约束
- 2\leq N \leq 20
- 1\leq M \leq N(N-1)
- 1\leq U_i,V_i \leq N
- U_i \neq V_i
- (U_i,V_i) \neq (U_j,V_j) 为 i\neq j
- -10^6\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
输出
如果存在至少访问每个顶点一次的步行,则打印所遍历边的最小总权重。否则,打印 No.
示例输入 1
3 4 1 2 5 2 1 -3 2 3 -4 3 1 100
示例输出 1
-2
按顺序跟踪顶点 2\rightarrow 1\rightarrow 2\rightarrow 3,可以至少访问所有顶点一次,遍历的边的总权重为 (-3)+5+(-4)=-2。 这是最小值。
示例输入 2
3 2 1 2 0 2 1 0
示例输出 2
No
不存在至少访问所有顶点一次的步行。
示例输入 3
5 9 1 2 -246288 4 5 -222742 3 1 246288 3 4 947824 5 2 -178721 4 3 -947824 5 4 756570 2 5 707902 5 1 36781
示例输出 3
-449429