題目 2426:
信息學奧賽一本通T1518-搶掠計劃
時間限制: 2s
內存限制: 192MB 提交: 10 解決: 4
題目描述
原題來自：APIO 2009
Siruseri 城中的道路都是單向的。不同的道路由路口連接。按照法律的規(guī)定，在每個路口都設立了一個 Siruseri 銀行的 ATM 取款機。令人奇怪的是，Siruseri 的酒吧也都設在路口，雖然并不是每個路口都設有酒吧。
Banditji 計劃實施 Siruseri 有史以來最驚天動地的 ATM 搶劫。他將從市中心出發(fā)，沿著單向道路行駛，搶劫所有他途徑的 ATM 機，最終他將在一個酒吧慶祝他的勝利。
使用高超的黑客技術，他獲知了每個 ATM 機中可以掠取的現(xiàn)金數(shù)額。他希望你幫助他計算從市中心出發(fā)最后到達某個酒吧時最多能搶劫的現(xiàn)金總數(shù)。他可以經(jīng)過同一路口或道路任意多次。但只要他搶劫過某個 ATM 機后，該 ATM 機里面就不會再有錢了。
例如，假設該城中有 66 個路口，道路的連接情況如下圖所示：
市中心在路口 1，由一個入口符號 → 來標識，那些有酒吧的路口用雙圈來表示。每個 ATM 機中可取的錢數(shù)標在了路口的上方。在這個例子中，Banditji 能搶劫的現(xiàn)金總數(shù)為 47，實施的搶劫路線是：1?2?4?1?2?3?5。
輸入格式
第一行包含兩個整數(shù) N,M。N 表示路口的個數(shù)，M 表示道路條數(shù)。
接下來 M 行，每行兩個整數(shù)，這兩個整數(shù)都在 1 到 N 之間，第 i+1 行的兩個整數(shù)表示第 i 條道路的起點和終點的路口編號。
接下來 N 行，每行一個整數(shù)，按順序表示每個路口處的 ATM 機中的錢數(shù)。
接下來一行包含兩個整數(shù) S,P，S 表示市中心的編號，也就是出發(fā)的路口。P 表示酒吧數(shù)目。
接下來的一行中有 P 個整數(shù)，表示 P 個有酒吧的路口的編號。
接下來 M 行，每行兩個整數(shù)，這兩個整數(shù)都在 1 到 N 之間，第 i+1 行的兩個整數(shù)表示第 i 條道路的起點和終點的路口編號。
接下來 N 行，每行一個整數(shù)，按順序表示每個路口處的 ATM 機中的錢數(shù)。
接下來一行包含兩個整數(shù) S,P，S 表示市中心的編號，也就是出發(fā)的路口。P 表示酒吧數(shù)目。
接下來的一行中有 P 個整數(shù)，表示 P 個有酒吧的路口的編號。
輸出格式
輸出一個整數(shù)，表示 Banditji 從市中心開始到某個酒吧結束所能搶劫的最多的現(xiàn)金總數(shù)。
樣例輸入
6 7 1 2 2 3 3 5 2 4 4 1 2 6 6 5 10 12 8 16 1 5 1 4 4 3 5 6
樣例輸出
47
提示
數(shù)據(jù)范圍與提示:
50% 的輸入保證 N,M≤3000。
100% 的輸入保證 N,M≤500000。
每個 ATM 機中可取的錢數(shù)為一個非負整數(shù)且不超過 4000。輸入數(shù)據(jù)保證你可以從市中心沿著 Siruseri 的單向的道路到達其中的至少一個酒吧。
50% 的輸入保證 N,M≤3000。
100% 的輸入保證 N,M≤500000。
每個 ATM 機中可取的錢數(shù)為一個非負整數(shù)且不超過 4000。輸入數(shù)據(jù)保證你可以從市中心沿著 Siruseri 的單向的道路到達其中的至少一個酒吧。