配点: 1000 点
問題文
在帕肯王国 N 城镇, M 书籍之路将他们连接起来。i 第二条路就是镇 A_i 卡拉町 移至 B_i 具有单向连接。 另外, P 在每个城镇 1 每个城镇都有观景台。 C_i 的观景台海拔高度为 它位于 D_i 。
ZRK 计划去兜风。他是镇上的 从 S 展望台出发,沿着几条道路行驶即可到达小镇。 在 T 处的观景台结束驾驶。 您经过同一个城镇或道路多少次并不重要。
如果他经过的城镇有观景台,ZRK 总是会停下来。 他的幸福是第一位的 0 不过出发时间以外还有观景台。 当我停在 i 时,我停在了之前的观景台。 与 j 的高程差的绝对值 |D_i - D_j| 你的幸福感会增加。
开车结束后他感到很高兴。 K 我想沿着上述路线行驶。 求满足该条件的最小路径长度。
然而,路线的长度是所有道路“您走过这条路多少次”的总和。例如,顶点
如果您沿着路线 3→5→2→4→3→5→4 行驶,则路线长度为 6 。
对于
如果幸福是
如果不存在大于或等于 K 的路由,则改为
请输出 -1 。
制約
- 所有输入均为整数。
- 2 \leq N \leq 50
- 1 \leq M \leq N(N-1)
- 1 \leq P \leq N
- 1 \leq S, T \leq N
- 1 \leq K \leq 10^9
- 1 \leq A_i , B_i \leq N (1 \leq i \leq M)
- A_i \neq B_i (1 \leq i \leq M)
- (A_i, B_i) \neq (A_j, B_j) (i \neq j)
- 1 \leq C_i \leq N (1 \leq i \leq P)
- 1 \leq D_i \leq 10^5 (1 \leq i \leq P)
- C_i \neq C_j (i \neq j)
- C_i = S 变为 i, C_j = T 变为 j 存在。
小課題
这项作业需要 2 有两个子作业。- (300 点) K \leq 20 很满意。
- (700分)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N M P S T K A_1 B_1 A_2 B_2 ... A_M B_M C_1 D_1 C_2 D_2 ... C_P D_P
出力
请输出满足条件的路径的最小长度。
如果不存在这样的路由,则改为 -1 。
入力例1
4 5 3 2 2 11 2 1 1 3 3 2 3 4 4 1 1 1 2 3 4 5
出力例1
6
最好按照以下路线出行。 转至
- 町 2 卡拉町 移至 1 。幸福是 |1-3|=2 增加。
- 町 1 卡拉町 移至 3 水至 4 。幸福是 |5-1|=4 增加。
- 町 4 卡拉町 移至 1 。幸福是 |1-5|=4 增加。
- 町 1 卡拉町 移至 3 水至 2 。幸福是 |3-1|=2 增加。
入力例2
3 2 2 1 3 5 1 2 2 3 1 1 3 3
出力例2
-1
入力例3
6 7 4 1 6 14 1 2 2 3 3 4 4 5 5 1 6 1 2 6 1 1 3 2 5 7 6 4
出力例3
7
作者: 秋鳗 通过重新排列获得的序列