TopCoder

Caido
Waimai

User's AC Ratio

81.2% (13/16)

Submission's AC Ratio

30.9% (29/94)

Tags

Description

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

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

但是,更換指針並不是不可能的。對於第 i 個節點,如果付 ai 元給管理員,則它會將指針往右搬動 xi 格,而如果付 bi 元給管理員,則他會將指針往右搬動 yi 格,對於第 i 個節點,移動指針的花費不能超過 ci 元。注意到,如果向右搬動之後超出該點的鐵道數量的話,會繞回第一條鐵道繼續搬動(也就是說,假設指針目前在 p ,第 i 個點出度為 di,那付一次 ai 元可以把 p 變為 (p+xi1) mod di+1,付一次 bi 元可以把 p 變為 (p+yi1) mod di+1)。可以付多次 aibi 來搬動指針

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

Input Format

第一行輸入一個整數 N ,表示車站數量。
接下來輸入 N 行,每行分別代表一個車站的鐵道。
i+1 行首先輸入一個整數 di,表示第 i 個車站的鐵道數量。接下來輸入 2×di 個整數,第 2j,2j+1 個整數分別代表該鐵道指向的車站以及泡泡紙數量 ti,j,wi,j

接下來輸入一行 N 個整數,分別代表 ai
接下來輸入一行 N 個整數,分別代表 xi
接下來輸入一行 N 個整數,分別代表 bi
接下來輸入一行 N 個整數,分別代表 yi
接下來輸入一行 N 個整數,分別代表 ci

對於所有測試資料:

  • 2N2×105
  • 1diN,di7×105
  • 1ti,jN
  • 1xi,yidi
  • 0ai,bi,wi,j109
  • 0ci<231

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+31) mod 4+1=4 條邊,再花 1 元把指針移動到第 (4+31) 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 ai=bi>ci 11
3 1, 12~21 xi=yi=1,bi=ai,N500 13
4 1, 12~31 xi=yi=1,bi=ai 15
5 0~1, 12~41 ai=bi,xi=yi 17
6 0~1, 12~21, 42~51 N500 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