在遊戲中有許多技能,
而技能間可能存在相依關係,也就是必須先解鎖前置技能,才能夠解鎖後面技能;
或者也可以購買技能書,就能夠忽略前置技能是否解鎖,而提前進到下個技能階段。
已知全部技能有 N 個(編號 0 ~ N-1),
以及 M 組技能相依關係 (u, v),也就是需要先解鎖技能 u 才能解鎖技能 v
假設現在購買了 K 本技能書 (a1, a2, ..., aK),
請協助計算包含初始技能書本身技能在內,最後總共可以解鎖幾種不同的技能。
以下圖為例,假設全部技能有 9 個,並購買了 技能 {1, 2, 3} 的技能書,
則最後總共可以解鎖 {1, 2, 3, 4, 5, 7} 共六種不同的技能
其中特別的是,對於技能 0 和技能 6,
雖然本身沒有任何前置技能,但因沒有受到所購買的技能書觸發,因此不會主動被解鎖。
第一行有三個正整數 N, M, K,
代表總技能數、技能相依關係數、已購買技能書數
1 ≤ N ≤ 1000
N-1 ≤ M ≤ 2*N
1 ≤ K ≤ 10
接著有 K 個數字 ai,代表已購買的技能書技能編號
0 ≤ ai ≤ N-1
最後有 M 行,每行有兩個整數 u 和 v,
代表需要先解鎖技能 u 才能解鎖技能 v
0 ≤ u,v ≤ N-1
包含初始技能書本身技能在內,
最後總共可以解鎖幾種不同的技能
9 8 3 1 2 3 0 1 1 5 2 3 3 4 5 4 4 7 6 8 7 8
6
10%:為直鏈,即相依關係為 (0, 1), (1, 2), ..., (N-2, N-1)
30%:K ≤ 3
60%:無特別限制
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|