分数: 433 分
问题陈述
高桥正在一个城市旅行 N 观光景点。观光景点编号为 1 to N,并且有 M 连接它们的双向道路。
各观光点 i 具有正整数值 P_i 叫做“满意”。高桥从观光地出发 S,他的酒店所在位置,并前往目的地、观光景点 T.
路 j 双向连接观光景点 U_j 和 V_j,并花费交通费 W_j 无论行驶方向如何。
高桥从观光地出发 S 并依序沿着道路到达观光景点 T。他可以多次经过同一条路或同一个旅游景点。
高桥的“利润”定义如下:
- 考虑沿路线访问的所有观光点的集合,包括起点 S 和目的地 T。利润为该集合中各景点的满意度值之和(每个景点计算一次)减去沿途所有道路的交通费总和。
- 即使多次访问同一个景点,其满意度值也仅增加一次。
- 如果多次穿越同一条道路,则每次穿越都会加收交通费。无论行驶方向如何,每经过一条道路都会产生一笔交通费。
求高桥从观光地出发时的最大收益 S 前往观光景点 T.
注意,不必要的穿越道路只会增加交通费用,而不会增加满意度,因此最大利润总是有限的。请注意,最大利润可能为负数。可以保证 T 可从 S.
约束
- 2 \leq N \leq 12
- 1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
- 1 \leq S \leq N
- 1 \leq T \leq N
- S \neq T
- 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
- 1 \leq W_j \leq 10^4 (1 \leq j \leq M)
- 连接任意一对旅游景点的道路最多有一条。
- 旅游景点 从观光景点可到达 T 从观光地可到达 S.
- 所有输入值均为整数。
输入
N M P_1 P_2 \ldots P_N S T U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
- 第一行包含 N、观光景点的数量以及 M,道路数量,以空格分隔。
- 第二行包含满意度值 各观光点的 P_1, P_2, \ldots, P_N ,以空格分隔。
- 第三行包含起点 S 和目标点 T,用空格分隔。
- 以下 M 线路提供道路信息。
- 的 (3 + j)第线包含观光景点 U_j, V_j 由 j第条路及其交通费 W_j,用空格分隔。
输出
在单行中输出最大利润。如果最大利润为负,则输出负值。
示例输入 1
3 3 10 20 30 1 3 1 2 5 2 3 5 1 3 25
示例输出 1
50
示例输入 2
5 7 10 20 30 40 50 1 5 1 2 3 1 4 10 2 3 4 2 4 7 2 5 3 3 5 8 4 5 6
示例输出 2
126
示例输入 3
8 10 5 50 50 50 50 50 50 5 1 8 1 2 2 1 8 100 2 3 3 3 4 3 4 5 1 4 8 4 5 6 1 6 7 1 7 8 5 2 8 50
示例输出 3
294