← 返回题目列表

AtCoder · abc164_e

E. 两种货币

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

分数: 500 点

问题陈述

有 N 城市编号 1 to N,通过连接 M 铁路。

您现在位于城市 1,与 10^{100} 金币和 S 银币在你的口袋里。

的 i-th铁路连接城市 U_i 和城市 V_i 双向,单程旅行费用 A_i 银币和需要 B_i 分钟。 您不能使用金币支付车费。

每个城市都有兑换柜台。在 City 的兑换柜台 i,可以得到 C_i 银币 1 金币。 交易需要 您给予的每枚金币都需要 D_i 分钟。 您可以在每个兑换柜台兑换任意数量的金币。

对于每个 t=2, ..., N,求从 City 出发所需的最短时间 1 前往城市 t。您可以忽略等待火车的时间。

约束

  • 2 \leq N \leq 50
  • N-1 \leq M \leq 100
  • 0 \leq S \leq 10^9
  • 1 \leq A_i \leq 50
  • 1 \leq B_i,C_i,D_i \leq 10^9
  • 1 \leq U_i < V_i \leq N
  • 没有对 i, j(i \neq j) 这样 (U_i,V_i)=(U_j,V_j).
  • 各城市 从城市可以到达 t=2,...,N 从市区可到达 1 拥有一定数量的铁路。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M S
U_1 V_1 A_1 B_1
:
U_M V_M A_M B_M
C_1 D_1
:
C_N D_N

输出

对于每个 t=2, ..., N 按照此顺序,打印一行,其中包含从 City 出发所需的最短时间 1 前往城市 t.


示例输入 1

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

示例输出 1

2
14

本输入中的铁路网如下图所示。

在此图中,每个城市的标记如下:

  • 第一行:身份证号码 i 的城市 (i 城市 i)
  • 第二行: C_i / D_i

同样,每条铁路的标签如下:

  • 第一行:身份证号码 i 铁路(i 为 i输入中的第 条铁路)
  • 第二行: A_i / B_i

Figure

您可以从城市出发 1 前往城市 2 in 2 分钟,如下:

  • 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 2 分钟。


您可以从城市出发 1 前往城市 3 in 14 分钟,如下:

  • 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 2 分钟。
  • 在城市兑换柜台 2, 交换 3 金币 3 银币 6 分钟。
  • 使用 1-st 铁路将从城市搬迁 2 前往城市 1 in 2 分钟。
  • 使用 2-nd 铁路将从城市迁出 1 前往城市 3 in 4 分钟。

示例输入 2

4 4 1
1 2 1 5
1 3 4 4
2 4 2 2
3 4 1 1
3 1
3 1
5 2
6 4

示例输出 2

5
5
7

本次输入的铁路网如下图所示:

Figure

您可以从城市出发 1 前往城市 4 in 7 分钟,如下:

  • 在城市兑换柜台 1, 交换 2 金币 6 银币 2 分钟。
  • 使用 2-nd 铁路将从城市迁出 1 前往城市 3 in 4 分钟。
  • 使用 4第 条铁路将从城市迁出 3 前往城市 4 in 1 分钟。

示例输入 3

6 5 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000
1 3000
1 700
1 100
1 1
100 1

示例输出 3

1
9003
14606
16510
16576

本次输入的铁路网如下图所示:

Figure

您可以从城市出发 1 前往城市 6 in 16576 分钟,如下:

  • 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 1 分钟。
  • 在城市兑换柜台 2, 交换 3 金币 3 银币 9000 分钟。
  • 使用 1-st 铁路将从城市搬迁 2 前往城市 1 in 1 分钟。
  • 使用 2-nd 铁路将从城市迁出 1 前往城市 3 in 1 分钟。
  • 在城市兑换柜台 3, 交换 8 金币 8 银币 5600 分钟。
  • 使用 2-nd 铁路将从城市迁出 3 前往城市 1 in 1 分钟。
  • 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 1 分钟。
  • 使用 3-rd铁路将从城市迁出 2 前往城市 4 in 1 分钟。
  • 在城市兑换柜台 4, 交换 19 金币 19 银币 1900 分钟。
  • 使用 3-rd铁路将从城市迁出 4 前往城市 2 in 1 分钟。
  • 使用 1-st 铁路将从城市搬迁 2 前往城市 1 in 1 分钟。
  • 使用 2-nd 铁路将从城市迁出 1 前往城市 3 in 1 分钟。
  • 使用 4第 条铁路将从城市迁出 3 前往城市 5 in 1 分钟。
  • 在城市兑换柜台 5, 交换 63 金币 63 银币 63 分钟。
  • 使用 4第 条铁路将从城市迁出 5 前往城市 3 in 1 分钟。
  • 使用 2-nd 铁路将从城市迁出 3 前往城市 1 in 1 分钟。
  • 使用 5第 条铁路将从城市迁出 1 前往城市 6 in 1 分钟。

示例输入 4

4 6 1000000000
1 2 50 1
1 3 50 5
1 4 50 7
2 3 50 2
2 4 50 4
3 4 50 3
10 2
4 4
5 5
7 7

示例输出 4

1
3
5

本次输入的铁路网如下图所示:

Figure


示例输入 5

2 1 0
1 2 1 1
1 1000000000
1 1

示例输出 5

1000000001

本次输入的铁路网如下图所示:

Figure

您可以从城市出发 1 前往城市 2 in 1000000001 分钟,如下:

  • 在城市兑换柜台 1, 交换 1 金币 1 银币 1000000000 分钟。
  • 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 1 分钟。