小夜丸的连夜出逃
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Problem Description
小夜丸站在自己地下迷宫的起点,她现在被追捕,要带上自己尽可能多的财宝跑路。
她的地下迷宫由n个点构成,每个点内有一定数量的财宝以及m个的单向传送门,每个可以把她传送到对应的点。
在某些点中有红色的逃脱按钮,她如果要逃脱必须要得到至少一个按钮。
小夜丸不知道到底最多能带走多少财宝于是就去求问OZDimensional,OZDimensional也不是很清楚于是求助与你,
起点为1。
请你求出小夜丸最多可以带走多少财宝离开,如果逃不走就输出-1。
Input Format
第一行输入三个整数,表示有个点,个传送门,个点放有逃脱按钮。
接下来行,每一行输入两个整数,表示有一个在点有一个通向点的单向传送门。
接下来行,每一行输入一个整数,按顺序表示在点有价值为w的财宝。例如在第一行就表示在第一个点中有价值为的财宝。
接下来行,每一行输入一个整数,表示点放有逃脱按钮。
保证传送门没有重复的并且。
Output Format
一行一个整数表示最大可以得到的价值总和,如果无法逃脱,输出-1。
Sample
输入
6 5 1
1 2
2 3
5 3
4 5
1 4
2
1
10
3
4
5
2
输出
13
Hint
$1 \le n \le 10^{5}, 1 \le m \le 3*10^{5}, 1 \le u,v,s,p \le n,1 \le w \le 5000$
重庆邮电大学第十六届ACM程序设计大赛(现场赛)
- 状态
- 已结束
- 规则
- XCPC
- 题目
- 12
- 开始于
- 2023-10-15 13:10
- 结束于
- 2023-10-15 18:10
- 持续时间
- 5 小时
- 主持人
- 参赛人数
- 0