101644: [AtCoder]ABC164 E - Two Currencies

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $500$ points

Problem Statement

There are $N$ cities numbered $1$ to $N$, connected by $M$ railroads.

You are now at City $1$, with $10^{100}$ gold coins and $S$ silver coins in your pocket.

The $i$-th railroad connects City $U_i$ and City $V_i$ bidirectionally, and a one-way trip costs $A_i$ silver coins and takes $B_i$ minutes. You cannot use gold coins to pay the fare.

There is an exchange counter in each city. At the exchange counter in City $i$, you can get $C_i$ silver coins for $1$ gold coin. The transaction takes $D_i$ minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.

For each $t=2, ..., N$, find the minimum time needed to travel from City $1$ to City $t$. You can ignore the time spent waiting for trains.

Constraints

  • $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$
  • There is no pair $i, j(i \neq j)$ such that $(U_i,V_i)=(U_j,V_j)$.
  • Each city $t=2,...,N$ can be reached from City $1$ with some number of railroads.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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$

Output

For each $t=2, ..., N$ in this order, print a line containing the minimum time needed to travel from City $1$ to City $t$.

Sample Input 1

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

Sample Output 1

2
14

The railway network in this input is shown in the figure below.

In this figure, each city is labeled as follows:

  • The first line: the ID number $i$ of the city ($i$ for City $i$)
  • The second line: $C_i$ / $D_i$

Similarly, each railroad is labeled as follows:

  • The first line: the ID number $i$ of the railroad ($i$ for the $i$-th railroad in input)
  • The second line: $A_i$ / $B_i$

Figure

You can travel from City $1$ to City $2$ in $2$ minutes, as follows:

  • Use the $1$-st railroad to move from City $1$ to City $2$ in $2$ minutes.


You can travel from City $1$ to City $3$ in $14$ minutes, as follows:

  • Use the $1$-st railroad to move from City $1$ to City $2$ in $2$ minutes.
  • At the exchange counter in City $2$, exchange $3$ gold coins for $3$ silver coins in $6$ minutes.
  • Use the $1$-st railroad to move from City $2$ to City $1$ in $2$ minutes.
  • Use the $2$-nd railroad to move from City $1$ to City $3$ in $4$ minutes.

Sample Input 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

Sample Output 2

5
5
7

The railway network in this input is shown in the figure below:

Figure

You can travel from City $1$ to City $4$ in $7$ minutes, as follows:

  • At the exchange counter in City $1$, exchange $2$ gold coins for $6$ silver coins in $2$ minutes.
  • Use the $2$-nd railroad to move from City $1$ to City $3$ in $4$ minutes.
  • Use the $4$-th railroad to move from City $3$ to City $4$ in $1$ minutes.

Sample Input 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

Sample Output 3

1
9003
14606
16510
16576

The railway network in this input is shown in the figure below:

Figure

You can travel from City $1$ to City $6$ in $16576$ minutes, as follows:

  • Use the $1$-st railroad to move from City $1$ to City $2$ in $1$ minute.
  • At the exchange counter in City $2$, exchange $3$ gold coins for $3$ silver coins in $9000$ minutes.
  • Use the $1$-st railroad to move from City $2$ to City $1$ in $1$ minute.
  • Use the $2$-nd railroad to move from City $1$ to City $3$ in $1$ minute.
  • At the exchange counter in City $3$, exchange $8$ gold coins for $8$ silver coins in $5600$ minutes.
  • Use the $2$-nd railroad to move from City $3$ to City $1$ in $1$ minute.
  • Use the $1$-st railroad to move from City $1$ to City $2$ in $1$ minute.
  • Use the $3$-rd railroad to move from City $2$ to City $4$ in $1$ minute.
  • At the exchange counter in City $4$, exchange $19$ gold coins for $19$ silver coins in $1900$ minutes.
  • Use the $3$-rd railroad to move from City $4$ to City $2$ in $1$ minute.
  • Use the $1$-st railroad to move from City $2$ to City $1$ in $1$ minute.
  • Use the $2$-nd railroad to move from City $1$ to City $3$ in $1$ minute.
  • Use the $4$-th railroad to move from City $3$ to City $5$ in $1$ minute.
  • At the exchange counter in City $5$, exchange $63$ gold coins for $63$ silver coins in $63$ minutes.
  • Use the $4$-th railroad to move from City $5$ to City $3$ in $1$ minute.
  • Use the $2$-nd railroad to move from City $3$ to City $1$ in $1$ minute.
  • Use the $5$-th railroad to move from City $1$ to City $6$ in $1$ minute.

Sample Input 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

Sample Output 4

1
3
5

The railway network in this input is shown in the figure below:

Figure

Sample Input 5

2 1 0
1 2 1 1
1 1000000000
1 1

Sample Output 5

1000000001

The railway network in this input is shown in the figure below:

Figure

You can travel from City $1$ to City $2$ in $1000000001$ minutes, as follows:

  • At the exchange counter in City $1$, exchange $1$ gold coin for $1$ silver coin in $1000000000$ minutes.
  • Use the $1$-st railroad to move from City $1$ to City $2$ in $1$ minute.

Input

题意翻译

## 题目描述 有 $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$ ## 输出格式 一个整数表示答案。

Source/Category

加入题单

上一题 下一题 算法标签：