← 返回题目列表

AtCoder · iroha2019_day2_g

G. 学校路线

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

配点: 600 点

問題文

*Kitamu 是帮助撰写此问题的人的名字。而且,Kitamu的女朋友不是伊吕波。

今天是北木和女友期待已久的“第一次一起采花”周年纪念日。他今天是 K 我应该送她一朵书花。然而,他有太多的纪念日需要处理,忘记了买花。于是他决定在上学的路上买些花。

在 Kitamu 居住的小镇上, 有 N 个站,每个站有 它的编号为 1~N 。另外,他使用的铁路是 M 有铁轨。 i 主线为收费站 C_i 日元2津野站 A_i 和 我讨厌 B_i 并且可以交换。车站 j 所以 X_j 书花一套 Y_j 用日元可以买任意数量的东西。他是车站 他住在 1 附近,他的学校在车站附近。 位于 N 附近。

好吧,我需要他。 K 购买超过一本书的鲜花后,到达学校的交通和鲜花的总费用最低是多少?

制約

  • 输入全为整数。
  • 2 \leq N \leq 1000
  • 1 \leq M \leq 2000
  • 1 \leq K \leq 1000
  • 1 \leq A_i,B_i \leq N (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • 0 \leq X_j \leq K (1 \leq j \leq N)
  • 1 \leq Y_j \leq 10^9 (1 \leq j \leq N)

2019/05/01 21:32 附录:一些限制 有一个错误,显示为 N 是 这将是第 M 、 M 是 这将是第 N ,因此已更正。


入力

输入是按以下格式从标准输入给出的。

N M K
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

北穆加 K 购买100多朵花后,将上学交通费和鲜花的最低总费用打印成一行。然而,花 K 如果您买不起更多的书或无法去学校 输出-1。


入力例 1

4 3 10
1 2 100
2 3 100
3 4 100
3 10
5 20
10 1000
1 8

出力例 1

338

駅 1 从车站 车站经 2 、駅 3 转至 4 。总运输成本为 300 变成日元。车站 1 在 3 设置,站 4 在 1 如果您购买一套,鲜花的总成本将为 38 变成日元。


入力例 2

4 4 3
1 2 50
2 3 50
3 4 100
3 1 100
2 500
2 200
2 500
2 500

出力例 2

600

鲜花购买 K 请注意,它可以不仅仅是一本书。


入力例 3

2 1 1
1 2 1
0 1
0 1

出力例 3

-1

入力例 4

10 16 10
6 10 3
3 1 4
2 3 9
8 8 8
10 4 10
6 5 9
2 3 1
7 4 3
8 2 2
6 10 9
8 6 10
8 3 4
7 8 2
6 4 6
8 7 9
9 6 7
5 10
4 3
7 7
1 8
3 8
5 1
6 3
1 7
2 8
7 8

出力例 4

22

解説

解説