AtCoder Beginner Contest 164
翻译中…
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$.
翻译中…
样例
Input #1
3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5
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$
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.
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
Output #2
5
5
7
The railway network in this input is shown in the figure below:
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.
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
Output #3
1
9003
14606
16510
16576
The railway network in this input is shown in the figure below:
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.
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
Output #4
1
3
5
The railway network in this input is shown in the figure below:
Input #5
2 1 0
1 2 1 1
1 1000000000
1 1
Output #5
1000000001
The railway network in this input is shown in the figure below:
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.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。