P2078 [第三章习题5.4]搬运计划
描述
Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定,
在每个路口都设立了一个Siruseri 银行的ATM 取款机。令人奇怪的是,Siruseri
的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。
Banditji 计划实施Siruseri 有史以来最惊天动地的ATM 抢劫。他将从市中心
出发,沿着单向道路行驶,抢劫所有他途径的ATM 机,最终他将在一个酒吧庆
祝他的胜利。
使用高超的黑客技术,他获知了每个ATM 机中可以掠取的现金数额。他希
望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可
以经过同一路口或道路任意多次。但只要他抢劫过某个ATM 机后,该ATM 机
里面就不会再有钱了。
例如,假设该城中有6 个路口,道路的连接情况如下图所示:
![](https://cdn.maxuetang.cn/ojimages/uploadFiles/image/20180731/20180731160529_772_htimg.png)
市中心在路口1,由一个入口符号→来标识,那些有酒吧的路口用双圈来表
示。每个ATM 机中可取的钱数标在了路口的上方。在这个例子中,Banditji 能抢
劫的现金总数为47,实施的抢劫路线是:1-2-4-1-2-3-5。
在每个路口都设立了一个Siruseri 银行的ATM 取款机。令人奇怪的是,Siruseri
的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。
Banditji 计划实施Siruseri 有史以来最惊天动地的ATM 抢劫。他将从市中心
出发,沿着单向道路行驶,抢劫所有他途径的ATM 机,最终他将在一个酒吧庆
祝他的胜利。
使用高超的黑客技术,他获知了每个ATM 机中可以掠取的现金数额。他希
望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可
以经过同一路口或道路任意多次。但只要他抢劫过某个ATM 机后,该ATM 机
里面就不会再有钱了。
例如,假设该城中有6 个路口,道路的连接情况如下图所示:
![](https://cdn.maxuetang.cn/ojimages/uploadFiles/image/20180731/20180731160529_772_htimg.png)
市中心在路口1,由一个入口符号→来标识,那些有酒吧的路口用双圈来表
示。每个ATM 机中可取的钱数标在了路口的上方。在这个例子中,Banditji 能抢
劫的现金总数为47,实施的抢劫路线是:1-2-4-1-2-3-5。
输入
第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。
接下来M行,每行两个整数,这两个整数都在1到N之间,
第i+1行的两个整数表示第i条道路的起点和终点的路口编号。
接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。
接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。
接下来的一行中有P个整数,表示P个有酒吧的路口的编号
N, M<=500000。每个ATM机中可取的钱数为一个非负整数且不超过4000。
输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
输出
输出一个整数,表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
样例输入
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
提示