垃圾佬要搞事

TimeLimit:10000MS  MemoryLimit:512MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

垃圾佬所在的城市的道路都是单向的。不同的道路由路口连接。在这里,每个路口都设立了一个银行的 ATM 取款机。其中的某些路口有设立酒吧。垃圾佬计划实施有史以来最惊天动地的 ATM抢劫。他将从市中心出发,沿着单向道路行驶,抢劫所有他途径中的ATM 机,最终他将在一个酒吧庆祝他的胜利。

据可靠消息,垃圾佬获知了每个ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。

例如,假设该城中有6个路口,道路的连接情况如下图所示: 

blob.png

市中心在路口 1,由一个入口符号→来标识,那些有酒吧的路口用双圈来表示。每个ATM机中可取的钱数标在了路口的上方。在这个例子中,垃圾佬能抢劫的现金总数为47,实施的抢劫路线是:1-2-4-1-2-3-5。

Input

第一行包含两个整数 N、M。N 表示路口的个数,M表示道路条数。接下来有M行,每行两个整数,这两个整数都在 1到 N 之间,第i+1 行的两个整数表示第i 条道路的起点和终点的路口编号。接下来 N 行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数 S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。接下来的一行中有 P个整数,表示P个有酒吧的路口的编号。

【数据范围】

0<N,M<=500000。

每个 ATM机中可取的钱数为一个非负整数且不超过 4000。输入数据保证你可以从市中心沿着城市的单向的道路到达其中的至少一个酒吧。

Output

输出一个整数,表示垃圾佬从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。 

SampleInput
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
SampleOutput
47
Submit
题目统计信息详细
总AC数3
通过人数3
尝试人数4
总提交量14
AC率21.43%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: