Two Currencies

题目描述

有 $N$ 个城市，编号为 $1$ 到 $N$，由 $M$ 条铁路相连。 你现在在城市 $1$，口袋里有 $10^{100}$ 个金币和 $S$ 个银币。 第 $i$ 条铁路双向连接城市 $U_i$ 和城市 $V_i$，单程需要支付 $A_i$ 个银币并耗时 $B_i$ 分钟。 你不能使用金币支付车费。 每个城市都有兑换处。在城市 $i$ 的兑换处，你可以用 $1$ 个金币兑换 $C_i$ 个银币。 每兑换 1 个金币需花费 $D_i$ 分钟的处理时间。 你可以在每个兑换处兑换任意数量的金币。 对于每个 $t=2, ..., N$，求从城市 $1$ 到城市 $t$ 所需的最短时间。你可以忽略等车的时间。

输入格式

输入按下述格式由标准输入给出： $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$，按此顺序输出一行，内容为从城市 $1$ 到城市 $t$ 的最短时间。

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

2
14

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

5
5
7

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

1
9003
14606
16510
16576

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

1
3
5

2 1 0
1 2 1 1
1 1000000000
1 1

1000000001

提示

$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 不存在满足 $(U_i,V_i)=(U_j,V_j)$ 的不同对 $i,j(i \neq j)$。 对于每个城市 $t=2,...,N$，都存在一条由若干条铁路组成的路径可以从城市 $1$ 到达该城市。 输入中的所有数值均为整数。下列输入对应的铁路网络如下面的图所示。 在该图中，每个城市标注如下：

第一行：城市的 ID 编号 $i$（表示城市 $i$） 第二行：$C_i$ / $D_i$

同样，每条铁路标注如下：

第一行：铁路的 ID 编号 $i$（表示输入中的第 $i$ 条铁路） 第二行：$A_i$ / $B_i$

你可以在 $2$ 分钟内从城市 $1$ 到达城市 $2$，过程如下：

使用第 $1$ 条铁路从城市 $1$ 到城市 $2$，耗时 $2$ 分钟。

你可以在 $14$ 分钟内从城市 $1$ 到达城市 $3$，过程如下：

使用第 $1$ 条铁路从城市 $1$ 到城市 $2$，耗时 $2$ 分钟。 在城市 $2$ 的兑换处用 $3$ 个金币兑换 $3$ 个银币，耗时 $6$ 分钟。 使用第 $1$ 条铁路从城市 $2$ 回到城市 $1$，耗时 $2$ 分钟。 使用第 $2$ 条铁路从城市 $1$ 到城市 $3$，耗时 $4$ 分钟。
该输入对应的铁路网络如下面的图所示： 你可以在 $7$ 分钟内从城市 $1$ 到达城市 $4$，过程如下：

在城市 $1$ 的兑换处用 $2$ 个金币兑换 $6$ 个银币，耗时 $2$ 分钟。 使用第 $2$ 条铁路从城市 $1$ 到城市 $3$，耗时 $4$ 分钟。 使用第 $4$ 条铁路从城市 $3$ 到城市 $4$，耗时 $1$ 分钟。
该输入对应的铁路网络如下面的图所示： 你可以在 $16576$ 分钟内从城市 $1$ 到达城市 $6$，过程如下：

使用第 $1$ 条铁路从城市 $1$ 到城市 $2$，耗时 $1$ 分钟。 在城市 $2$ 的兑换处用 $3$ 个金币兑换 $3$ 个银币，耗时 $9000$ 分钟。 使用第 $1$ 条铁路从城市 $2$ 回到城市 $1$，耗时 $1$ 分钟。 使用第 $2$ 条铁路从城市 $1$ 到城市 $3$，耗时 $1$ 分钟。 在城市 $3$ 的兑换处用 $8$ 个金币兑换 $8$ 个银币，耗时 $5600$ 分钟。 使用第 $2$ 条铁路从城市 $3$ 回到城市 $1$，耗时 $1$ 分钟。 使用第 $1$ 条铁路从城市 $1$ 到城市 $2$，耗时 $1$ 分钟。 使用第 $3$ 条铁路从城市 $2$ 到城市 $4$，耗时 $1$ 分钟。 在城市 $4$ 的兑换处用 $19$ 个金币兑换 $19$ 个银币，耗时 $1900$ 分钟。 使用第 $3$ 条铁路从城市 $4$ 回到城市 $2$，耗时 $1$ 分钟。 使用第 $1$ 条铁路从城市 $2$ 回到城市 $1$，耗时 $1$ 分钟。 使用第 $2$ 条铁路从城市 $1$ 到城市 $3$，耗时 $1$ 分钟。 使用第 $4$ 条铁路从城市 $3$ 到城市 $5$，耗时 $1$ 分钟。 在城市 $5$ 的兑换处用 $63$ 个金币兑换 $63$ 个银币，耗时 $63$ 分钟。 使用第 $4$ 条铁路从城市 $5$ 回到城市 $3$，耗时 $1$ 分钟。 使用第 $2$ 条铁路从城市 $3$ 回到城市 $1$，耗时 $1$ 分钟。 使用第 $5$ 条铁路从城市 $1$ 到城市 $6$，耗时 $1$ 分钟。
该输入对应的铁路网络如下面的图所示：
该输入对应的铁路网络如下面的图所示： 你可以在 $1000000001$ 分钟内从城市 $1$ 到达城市 $2$，过程如下：

在城市 $1$ 的兑换处用 $1$ 个金币兑换 $1$ 个银币，耗时 $1000000000$ 分钟。 使用第 $1$ 条铁路从城市 $1$ 到城市 $2$，耗时 $1$ 分钟。

标签: AtCoder|abc164E

来源

AtCoder|abc164E