[TJOI2019]大中锋的游乐场

题目背景

TJOI2019 D2T1 源文件名:park.* 时间限制: 1s 内存限制: 128M

题目描述

大中锋正在一个游乐场里玩耍。游乐场里有很多娱乐设施,娱乐设施之间相互有道路相连,经过每一条路都需要花费一定的时间。为了方便游客,每一个娱乐设施旁都会配有一个小卖部,一部分小卖部会销售可乐,另一部分会销售汉堡。 由于大中锋十分贪吃,所以每当他走到一个娱乐设施,他都会先去购买一杯可乐或一个汉堡,并把它们吃掉。但如果大中锋吃掉的汉堡数量比他喝掉的可乐数量多于 $k$ ,那他就会感到很渴;如果喝掉的可乐数量比吃掉的汉堡数量多于 $k$ ,那他就会感到很饿。 现在大中锋正在第 $a$ 个娱乐设施,他想前往第 $b$ 个娱乐设施,但在他前进的路途中他不希望自己很渴或很饿。大中锋想知道自己在路上少花费多少时间。但由于大中锋很懒惰,他不想思考这个问题。你能帮助他解决这个问题吗? 注意:大中锋非常贪吃,所以他到达每个点的第一件事是去吃(或者喝),才考虑其他的事情,所以在起始点和终点他都会去买汉堡(可乐),你也需要保证在这两个点他不会感到很饿或者很渴。

输入输出格式

输入格式


多样例输入,第一行输入一个正整数 $T$ 表示样例数。 对于每一个样例: 第一行三个数字 $n,m,k$ , $n$ 代表游乐场一共有多少个娱乐设施, $m$ 代表游乐场一共有多少条道路, $k$ 的意义如题面中所述。接下来有一行 $n$ 个数字,第 $i$ 个数字代表第 $i$ 个小卖部销售的是什么, $1$ 代表可乐, $2$ 代表汉堡。接下来有 $m$ 行输入,每行三个数字 $p,q,t$ ,代表从第 $p$ 个娱乐设施到第 $q$ 个娱乐设施有一条双向道路,通过这条道路需要花费 $t$ 单位时间。最后一行有两个整数 $a,b$ ,代表大中锋想从娱乐设施 $a$ 前往娱乐设施 $b$ 。

输出格式


每组样例输出一行整数 $t$ ,代表大中锋在路上既不会感到很渴也不会感到很饿的情况下,从娱乐设施 $a$ 到娱乐设施 $b$花费的最少时间,如果无法达到,输出 $-1$ 。

输入输出样例

输入样例 #1

1
2 1 1
1 1
1 2 1
1 2

输出样例 #1

-1

输入样例 #2

1
2 1 2
1 1
1 2 1
1 2

输出样例 #2

1

说明

### 数据范围 ### 对于 $30\%$ 的数据, $n\leq 50,m\leq 1000$ 对于 $100\%$ 的数据, $n\leq 10000,m\leq 100000,k\leq 10,t\leq 10000$ 对于所有数据,保证 $T ≤ 10$ ,且每个样例点的大数据不超过 $2$ 个。 ### 题目补充说明 ### - 路径不一定是简单路径 - 大中锋可以多次经过一个节点,同时每次都会取得汉堡/可乐