TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

80.0% (12/15)

Submission's AC Ratio

30.1% (28/93)

Tags

Description

你是一位列車長,正在駕駛著一台火車開往左營。但是,不知名的魔法師施法讓鐵道上充滿了紓壓好玩的泡泡紙。

火車路網圖可以由一張有 $N$ 個節點的有向圖表示,其中,左營的編號為 $N$ 。對於第 $i$ 個節點的第 $j$ 條邊,它會有兩個參數 $t_{i,j},w_{i,j}$ ,分別表示那一條鐵道指向的節點以及這條鐵道的泡泡紙數量。
此外,對於每一個節點,剛開始時會由一個指針指著自己的第 $1$ 條鐵道。當火車抵達這個節點的時候,如果該節點不是 $N$ 號點,則火車會走向指針所指的鐵道。

但是,更換指針並不是不可能的。對於第 $i$ 個節點,如果付 $a_i$ 元給管理員,則它會將指針往右搬動 $x_i$ 格,而如果付 $b_i$ 元給管理員,則他會將指針往右搬動 $y_i$ 格,對於第 $i$ 個節點,移動指針的花費不能超過 $c_i$ 元。注意到,如果向右搬動之後超出該點的鐵道數量的話,會繞回第一條鐵道繼續搬動(也就是說,假設指針目前在 $p$ ,第 $i$ 個點出度為 $d_i$,那付一次 $a_i$ 元可以把 $p$ 變為 $(p+x_i-1)\text{ mod }d_i+1$,付一次 $b_i$ 元可以把 $p$ 變為 $(p+y_i-1)\text{ mod }d_i+1$)。可以付多次 $a_i$ 與 $b_i$ 來搬動指針

身為一位盡責的列車長,當你從出發站前往左營時,你抵達左營所經過的距離必須是在所有合法移動指針的方法中,該點至左營的最短距離,也就是說,不能存在一條路徑長度比你所走的路徑還要短。
你最喜歡泡泡紙被火車那強壯有力的輪子輾過所發出的哀嚎了,因此,你想要知道,對於所有車站,如果你都沿著最短路徑走,並且在第 $i$ 個車站花費不超過 $c_i$ 元,則你最多可以壓過多少張泡泡紙?
但是,鐵路會有無法抵達左營的情況,或者是無法在各節點花費分別不超過 $c_i$ 的情況抵達的狀況,此時,請輸出 -1。

Input Format

第一行輸入一個整數 $N$ ,表示車站數量。
接下來輸入 $N$ 行,每行分別代表一個車站的鐵道。
第 $i+1$ 行首先輸入一個整數 $d_i$,表示第 $i$ 個車站的鐵道數量。接下來輸入 $2 \times d_i$ 個整數,第 $2j,2j+1$ 個整數分別代表該鐵道指向的車站以及泡泡紙數量 $t_{i,j},w_{i,j}$。

接下來輸入一行 $N$ 個整數,分別代表 $a_i$。
接下來輸入一行 $N$ 個整數,分別代表 $x_i$。
接下來輸入一行 $N$ 個整數,分別代表 $b_i$。
接下來輸入一行 $N$ 個整數,分別代表 $y_i$。
接下來輸入一行 $N$ 個整數,分別代表 $c_i$。

對於所有測試資料:

  • $2 \le N \le 2 \times 10 ^ 5$
  • $1\le d_i\le N,\sum d_i \le 7 \times 10 ^ 5$
  • $1 \le t_{i,j} \le N$
  • $1 \le x_i,y_i \le d_i$
  • $0 \le a_i,b_i,w_{i,j} \le 10 ^ 9$
  • $0\le c_i<2^ {31}$

Output Format

輸出 $N$ 行,第 $i$ 行代表在所有合法移動指針的方法中,由第 $i$ 個節點沿著最短路徑到左營,可以壓過的最大泡泡紙數量。
如果無解請輸出 -1。

Sample Input 1

6
4 3 3 5 5 4 4 2 2
1 6 2
1 6 3
1 6 4
1 6 5
1 1 100
1 1 1 1 1 1
3 1 1 1 1 1
1 1 1 1 1 1
3 1 1 1 1 1
2 0 0 0 0 0

Sample Output 1

8
2
3
4
5
0

Sample Input 2

2
1 1 1
1 2 2
1 1
1 1
1 1
1 1
1 1

Sample Output 2

-1
0

Hints

對於第一筆範例的第一個點,最佳解為先花費 $1$ 元把指針由第一條鐵道改到第 $(1+3-1)\text{ mod }4 +1 = 4$ 條邊,再花 $1$ 元把指針移動到第 $(4+3-1)\text{ mod }4+1 = 3$ 條邊。之後移動到 $4$ 號點。在 $4$ 號點不花錢,直接移動到 $6$ 號點。路上輾過 $8$ 張泡泡紙。
對於 $6$ 號點,由於本身就是左營故最短路徑為 $0$,因此不能移動。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~11 $a_i = b_i > c_i$ 11
3 1, 12~21 $x_i = y_i= 1,b_i = a_i,N \le 500$ 13
4 1, 12~31 $x_i = y_i = 1,b_i = a_i$ 15
5 0~1, 12~41 $a_i = b_i,x_i = y_i$ 17
6 0~1, 12~21, 42~51 $N \le 500$ 19
7 0~61 無其他限制 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1048576 65536 1 5 6 7
1 3000 1048576 65536 1 3 4 5 6 7
2 3000 1048576 65536 2 7
3 3000 1048576 65536 2 7
4 3000 1048576 65536 2 7
5 3000 1048576 65536 2 7
6 3000 1048576 65536 2 7
7 3000 1048576 65536 2 7
8 3000 1048576 65536 2 7
9 3000 1048576 65536 2 7
10 3000 1048576 65536 2 7
11 3000 1048576 65536 2 7
12 3000 1048576 65536 3 4 5 6 7
13 3000 1048576 65536 3 4 5 6 7
14 3000 1048576 65536 3 4 5 6 7
15 3000 1048576 65536 3 4 5 6 7
16 3000 1048576 65536 3 4 5 6 7
17 3000 1048576 65536 3 4 5 6 7
18 3000 1048576 65536 3 4 5 6 7
19 3000 1048576 65536 3 4 5 6 7
20 3000 1048576 65536 3 4 5 6 7
21 3000 1048576 65536 3 4 5 6 7
22 3000 1048576 65536 4 5 7
23 3000 1048576 65536 4 5 7
24 3000 1048576 65536 4 5 7
25 3000 1048576 65536 4 5 7
26 3000 1048576 65536 4 5 7
27 3000 1048576 65536 4 5 7
28 3000 1048576 65536 4 5 7
29 3000 1048576 65536 4 5 7
30 3000 1048576 65536 4 5 7
31 3000 1048576 65536 4 5 7
32 3000 1048576 65536 5 7
33 3000 1048576 65536 5 7
34 3000 1048576 65536 5 7
35 3000 1048576 65536 5 7
36 3000 1048576 65536 5 7
37 3000 1048576 65536 5 7
38 3000 1048576 65536 5 7
39 3000 1048576 65536 5 7
40 3000 1048576 65536 5 7
41 3000 1048576 65536 5 7
42 3000 1048576 65536 6 7
43 3000 1048576 65536 6 7
44 3000 1048576 65536 6 7
45 3000 1048576 65536 6 7
46 3000 1048576 65536 6 7
47 3000 1048576 65536 6 7
48 3000 1048576 65536 6 7
49 3000 1048576 65536 6 7
50 3000 1048576 65536 6 7
51 3000 1048576 65536 6 7
52 3000 1048576 65536 7
53 3000 1048576 65536 7
54 3000 1048576 65536 7
55 3000 1048576 65536 7
56 3000 1048576 65536 7
57 3000 1048576 65536 7
58 3000 1048576 65536 7
59 3000 1048576 65536 7
60 3000 1048576 65536 7
61 3000 1048576 65536 7