2 人解决，19 人已尝试。
11 份提交通过，共有 205 份提交。
9.8 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
战争时期，防空洞具有重要作用，当防空警报响起时，大家跑进最近的防空洞避难。但如果防空洞容量不够大的话，这样往往会造成一些人的无谓牺牲。比如有 A、B、C 三个防空洞，如果 A 的容量和 B 的容量比较小，B 处的人可以选择不进入防空洞 B，而进入防空洞 C(如果时间允许)，把 B 处的空间留给 A 处的人，这样让 A 处的人能进入 B 避难 (如果时间允许)。
请为 X 国的国防部设计一个能程序，对于给定的 N 个地方的人数和 N 处防空洞容量以及它们之间的连接情况，计算出所有人都进入防空洞所需的最少时间。靠你了，人民的救星！
以两个正整数 N(1<=N<=200),M(1<=M<=1500) 开始，表示有 N 个地点，M 条路。
接下来 N 行每行整数 ai,bi 表示第 i 个地方有 ai(0<=ai<=1000) 个人，该处防空洞容量为 bi(0<=bi<=1000)。
接下来 M 行每行三个整数 a,b,c，表示 a 与 b 之间有一条路 (无向的)，走这条路所需的时间为 c(1<=c<=1000000000)。
输出所有人都进入防空洞最少需要的时间。如果不可能所有人都进入防空洞，输出-1。
3 4 7 2 0 4 2 6 1 2 40 3 2 70 2 3 90 1 3 120
110
2 人解决，19 人已尝试。
11 份提交通过，共有 205 份提交。
9.8 EMB 奖励。
创建: 16 年，7 月前.
修改: 7 年，2 月前.
最后提交: 4 年前.
来源: N/A