题目描述(ID:12379)
标题: 光脑连接装置
标签:
详情: 啊哈沃德的“光脑连接装置”被偷走了!“光脑连接装置”上有重要的资料不能丢失。幸好 啊哈沃德打开了“查找我的光脑连接装置”这个功能,可以追踪小偷的位置。
编程星球被分成了 N 个区域。各个区域被编号为 1,2...N。其中 1 号区域是一个交通枢 纽,啊哈沃德就是在这里丢了“光脑连接装置”。有 M 条边将各个区域连接起来,两个区域之 间只有一条路,啊哈沃德从一个区域走到另一个区域需要花费 1 分钟。


至于小偷,他在偷到“光脑连接装置”后,会从区域 1 出发,一路前往区域 E 销赃,其中 将会经过P个区域。即沿着1->S ->S ->S ->...->->E的路径沿途寻找潜在的销赃者。


123
在Si 地区,他要待TSi分钟后确认这个区域没有人帮他销赃,他才会去往下一个区域。但是一旦


到达 E 点,一定会有人替他销赃。
啊哈沃德在“光脑连接装置”被偷后 G 分钟发现“光脑连接装置”被偷并回到了 1 号区域。
每一分钟啊哈沃德可以选择走到下一个区域或者保持呆在原区域不动。请求出啊哈沃德出发后 最少需要多少分钟可以追上小偷。





输入格式:
第一行五个整数:N, M, P, E, G。
第M+2行有P个数,分别表示 S1 S2 S3...Sp
第 M + 3 行也有 P 个数,分别表示 Ts1,Ts2,Ts3...Tsp
输出格式:
一个整数,啊哈沃德出发后最少需要多少分钟可以追上小偷。 如果他没办法追上小偷,输出“Failed”不需要输出双引号。
限制: 对于60%的数据,1<=N<=100, 1<=M<=6000,1<=P<=80
对于100%的数据,1<=N<=10000,1<=M<=800000, 1<=P<=1000
样例:

输入

6 8 5 4 1
1 2
1 5
4 3
3 6
2 3
3 5
5 6
4 6
2 3 5 6 3
1 1 2 1 3

输出

1

解释

第 0 分钟:啊哈沃德“光脑连接装置”被偷,但是啊哈沃德没有发现,小偷此时已经从 1号区域到达 2 号区域。
第 0-1 分钟:小偷在 2 号区域停留。
第 1 分钟:啊哈沃德发现“光脑连接装置”被偷,小偷在 2 号区域已经停留了 1 分钟,移 动到 3 号区域。
第 1-2 分钟:小偷在 3 号区域停留,啊哈沃德从 1 号区域前往 5 号区域。
第 2 分钟:啊哈沃德到达 5 号区域,小偷在 3 号区域已经停留 1 分钟,移动到 5 号区域。 啊哈沃德和小偷相遇,啊哈沃德揍扁了小偷。
因此啊哈沃德出发后 1 分钟就追上了小偷。

输入

9 13 7 6 10
1 2
2 9
9 3
3 8
3 4
1 8
8 4
9 7
3 7
4 7
4 5
4 6
5 6
8 3 9 7 3 4 5
1 3 3 5 3 2 1

输出

2
登录并解答