← 返回题目列表

AtCoder · tkppc4_2_j

J. 驱动器跳闸

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

配点: 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 有两个子作业。
  1. (300 点) K \leq 20 很满意。
  2. (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

作者: 秋鳗 通过重新排列获得的序列