你是一位列車長,正在駕駛著一台火車開往左營。但是,不知名的魔法師施法讓鐵道上充滿了紓壓好玩的泡泡紙。
火車路網圖可以由一張有 $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。
第一行輸入一個整數 $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$。
對於所有測試資料:
輸出 $N$ 行,第 $i$ 行代表在所有合法移動指針的方法中,由第 $i$ 個節點沿著最短路徑到左營,可以壓過的最大泡泡紙數量。
如果無解請輸出 -1。
對於第一筆範例的第一個點,最佳解為先花費 $1$ 元把指針由第一條鐵道改到第 $(1+3-1)\text{ mod }4 +1 = 4$ 條邊,再花 $1$ 元把指針移動到第 $(4+3-1)\text{ mod }4+1 = 3$ 條邊。之後移動到 $4$ 號點。在 $4$ 號點不花錢,直接移動到 $6$ 號點。路上輾過 $8$ 張泡泡紙。
對於 $6$ 號點,由於本身就是左營故最短路徑為 $0$,因此不能移動。
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 |