← 返回题目列表

AtCoder · awc0016_e

E. 观光旅游的最佳路线

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

分数: 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