AT_abc164_e [ABC164E] Two Currencies

题目描述

有 $n$ 个城市，它们由 $m$ 条双向道路连接，保证它们能够彼此到达。第 $i$ 条道路连接 $u_i,v_i$，需要花费 $x_i$ 个银币，耗费 $t_i$ 秒的时间。每个城市处都有兑换银币处，第 $i$ 个城市中你可以用 $1$ 个金币兑换 $c_i$ 个银币，可以兑换无限次，不过兑换 $1$ 次需要花费 $d_i$ 秒的时间。你一开始在 $1$ 号城市，有 $s$ 个银币和无限多的金币，求到其它城市需要耗费的最小时间。

$1 \leq n \leq 50$，$n - 1 \le m \le 100$，$1 \leq x_i \leq 50$，$1 \leq t_i,d_i \leq 10^9$，$1 \leq s,c_i \leq 10^9$

输入格式

• 第一行 $n,m,s$
• 接下来 $m$ 行 $u_i,v_i,x_i,t_i$
• 接下来 $n$ 行 $c_i,d_i$

输出格式

输出 $n - 1$ 行，第 $i$ 行一个整数表示到第 $i + 1$ 个城市耗费的最小时间。

输入输出样例 #1

输入 #1

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

输出 #1

2
14

输入输出样例 #2

输入 #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

输入输出样例 #3

输入 #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

输入输出样例 #4

输入 #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

输入输出样例 #5

输入 #5

2 1 0
1 2 1 1
1 1000000000
1 1

输出 #5

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)$ は存在しない
• 都市 $1$ から都市 $t=2,...,N$ にいくつかの鉄道路線を使って移動することができる。
• 入力はすべて整数である。

Sample Explanation 1

この入力中の鉄道網は以下のようなものです。 ここで、図中の都市のラベルは - 一段目に都市の番号 $i$ - 二段目に $C_i\ /\ D_i$ の形式に従っています。同様に、鉄道路線のラベルは - 一段目に鉄道路線の番号 $i$ - 二段目に $A_i\ /\ B_i$ の形式に従っています。  以下のように行動することで、 都市 $1$ から都市 $2$ へ $2$ 分で移動できます。 - $1$ 番目の鉄道路線を使って、都市 $1$ から都市 $2$ へ移動する。(所要時間: $2$ 分) 以下のように行動することで、 都市 $1$ から都市 $3$ へ $14$ 分で移動できます。 - $1$ 番目の鉄道路線を使って、都市 $1$ から都市 $2$ へ移動する。(所要時間: $2$ 分) - 都市 $2$ の両替所で、金貨 $3$ 枚を銀貨 $3$ 枚と交換する。(所要時間: $6$ 分) - $1$ 番目の鉄道路線を使って、都市 $2$ から都市 $1$ へ移動する。(所要時間: $2$ 分) - $2$ 番目の鉄道路線を使って、都市 $1$ から都市 $3$ へ移動する。(所要時間: $4$ 分)

Sample Explanation 2

この入力中の鉄道網は以下のようなものです。  以下のように行動することで、 都市 $1$ から都市 $4$ へ $7$ 分で移動できます。 - 都市 $1$ の両替所で、金貨 $2$ 枚を銀貨 $6$ 枚と交換する。(所要時間: $2$ 分) - $2$ 番目の鉄道路線を使って、都市 $1$ から都市 $3$ へ移動する。(所要時間: $4$ 分) - $4$ 番目の鉄道路線を使って、都市 $3$ から都市 $4$ へ移動する。(所要時間: $1$ 分)

Sample Explanation 3

この入力中の鉄道網は以下のようなものです。  以下のように行動することで、 都市 $1$ から都市 $6$ へ $16576$ 分で移動できます。 - $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$ 分)

Sample Explanation 4

この入力中の鉄道網は以下のようなものです。 

Sample Explanation 5

この入力中の鉄道網は以下のようなものです。  以下のように行動することで、 都市 $1$ から都市 $2$ へ $1000000001$ 分で移動できます。 - 都市 $1$ の両替所で、金貨 $1$ 枚を銀貨 $1$ 枚と交換する。(所要時間: $1000000000$ 分) - $1$ 番目の鉄道路線を使って、都市 $1$ から都市 $2$ へ移動する。(所要時間: $1$ 分)