缩点+spfa最长路【bzoj】 1179: [Apio2009]Atm
2021-07-07 22:08
阅读：622
Description
Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定， 在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心 出发，沿着单向道路行驶，抢劫所有他
途径的 ATM 机，最终他将在一个酒吧庆 祝他的胜利。使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希 望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可 以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机 里面就不会再有钱了。
Input
第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。
接下来M行，每行两个整数，这两个整数都在1到N之间，
第i+1行的两个整数表示第i条道路的起点和终点的路口编号。
接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。
接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。
接下来的一行中有P个整数，表示P个有酒吧的路口的编号
N, M
输入数据保证你可以从市中心沿着Siruseri的单向的道路到达其中的至少一个酒吧。
Output
输出一个整数，表示Banditji从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：缩点+spfa最长路【bzoj】 1179: [Apio2009]Atm
文章链接：http://soscw.com/index.php/essay/102218.html
文章标题：缩点+spfa最长路【bzoj】 1179: [Apio2009]Atm
文章链接：http://soscw.com/index.php/essay/102218.html
评论
亲，登录后才可以留言！