E - Optimal Route for a Sightseeing Tour Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は N 個の観光スポットがある街を旅行しています。観光スポットには 1 から N までの番号が付けられており、観光スポット間を結ぶ M 本の双方向の道路があります。

各観光スポット i には「満足度」と呼ばれる正の整数値 P_i が設定されています。高橋君はホテルのある観光スポット S からスタートし、目的地である観光スポット T へ向かいます。

道路 j は観光スポット U_j と V_j を双方向に結んでおり、どちらの向きに通過しても交通費 W_j がかかります。

高橋君は観光スポット S を出発し、道路を順にたどって観光スポット T に到着します。このとき、同じ道路や同じ観光スポットを何度通ってもかまいません。

高橋君の「利得」を次のように定義します。

  • 出発地 S および到着地 T を含め、経路上で通過したすべての観光スポットの集合を考える。この集合に含まれる各観光スポットの満足度を 1 回ずつ合計した値から、経路上で通過した道路の交通費の合計値を引いた値を利得とする。
  • 同じ観光スポットを複数回通過した場合でも、その観光スポットの満足度は 1 回分のみ加算される。
  • 同じ道路を複数回通過した場合は、通過した回数分だけ交通費が加算される。道路の通過方向によらず、同じ道路を通過するたびに 1 回分の交通費がかかる。

高橋君が観光スポット S から観光スポット T まで移動するとき、利得の最大値を求めてください。

なお、同じ道路を無駄に通過するほど交通費が増える一方で満足度は増えないため、利得の最大値は必ず有限に定まります。利得の最大値が負になる場合もあることに注意してください。S から T へ到達可能であることは保証されます。

制約

  • 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)
  • 同じ観光スポットの組を結ぶ道路は高々 1 本である。
  • 観光スポット S から観光スポット T へ到達可能である。
  • 入力はすべて整数で与えられる。

入力

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
  • 1 行目には、観光スポットの数を表す N と、道路の数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各観光スポットの満足度を表す P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
  • 3 行目には、スタート地点を表す S と、ゴール地点を表す T が、スペース区切りで与えられる。
  • 4 行目から M 行にわたって、道路の情報が与えられる。
  • 3 + j 行目では、 j 番目の道路が結ぶ観光スポット U_j , V_j と、その交通費 W_j が、スペース区切りで与えられる。

出力

利得の最大値を 1 行で出力せよ。なお、利得の最大値が負になる場合は負の値を出力すること。

入力例 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

Score : 433 pts

Problem Statement

Takahashi is traveling in a city with N sightseeing spots. The sightseeing spots are numbered from 1 to N, and there are M bidirectional roads connecting them.

Each sightseeing spot i has a positive integer value P_i called "satisfaction." Takahashi starts from sightseeing spot S, where his hotel is located, and heads to his destination, sightseeing spot T.

Road j bidirectionally connects sightseeing spots U_j and V_j, and costs a transportation fee of W_j regardless of the direction of travel.

Takahashi departs from sightseeing spot S and follows roads sequentially to arrive at sightseeing spot T. He may pass through the same road or the same sightseeing spot any number of times.

Takahashi's "profit" is defined as follows:

  • Consider the set of all sightseeing spots visited along the route, including the starting point S and the destination T. The profit is the sum of the satisfaction values of each sightseeing spot in this set (counted once each) minus the total transportation fees of all roads traversed along the route.
  • Even if the same sightseeing spot is visited multiple times, its satisfaction value is added only once.
  • If the same road is traversed multiple times, the transportation fee is added for each traversal. Regardless of the direction of travel, each traversal of a road incurs one transportation fee.

Find the maximum profit when Takahashi travels from sightseeing spot S to sightseeing spot T.

Note that traversing roads unnecessarily only increases transportation fees without increasing satisfaction, so the maximum profit is always finite. Be aware that the maximum profit may be negative. It is guaranteed that T is reachable from S.

Constraints

  • 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)
  • There is at most one road connecting any pair of sightseeing spots.
  • Sightseeing spot T is reachable from sightseeing spot S.
  • All input values are integers.

Input

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
  • The first line contains N, the number of sightseeing spots, and M, the number of roads, separated by a space.
  • The second line contains the satisfaction values P_1, P_2, \ldots, P_N of each sightseeing spot, separated by spaces.
  • The third line contains the starting point S and the goal point T, separated by a space.
  • The following M lines provide road information.
  • The (3 + j)-th line contains the sightseeing spots U_j, V_j connected by the j-th road and its transportation fee W_j, separated by spaces.

Output

Output the maximum profit in a single line. If the maximum profit is negative, output a negative value.

Sample Input 1

3 3
10 20 30
1 3
1 2 5
2 3 5
1 3 25

Sample Output 1

50

Sample Input 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

Sample Output 2

126

Sample Input 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

Sample Output 3

294