#P2402. 奶牛隐藏
奶牛隐藏
题目背景
这本是一个非常简单的问题,然而奶牛们由于下雨已经非常混乱,无法完成这一计算,于是这个任务就交给了你。(奶牛混乱的原因看题目描述)
题目描述
在一个农场里有 块田地。某天下午,有一群牛在田地里吃草,他们分散在农场的诸多田地上,农场由 条无向的路连接,每条路有不同的长度。
突然,天降大雨,奶牛们非常混乱,想要快点去躲雨。已知每个田地都建立有一个牛棚,但是每个牛棚只能容纳一定数量的牛躲雨,如果超过这个数量,那多出的牛只能去别的田地躲雨。奶牛们每移动 的距离花费 时间,奶牛们想知道它们全部都躲进牛棚,最少需要多少时间。(即最后一头奶牛最少要花多久才能躲进牛棚)。
输入格式
第一行有两个整数,分别代表田地数 和道路数 。
接下来 行,每行两个整数,第 行的整数 分别表示第 块田地的牛的数量以及该田地的牛棚最多可以容纳多少牛。
接下来 行,每行三个整数 ,代表存在一条长度为 的连接 和 的道路。
输出格式
输出一行一个整数表示所有奶牛全都躲进牛棚所用的最少时间。如果无法使全部奶牛都躲进牛棚,输出 。
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
110
提示
样例输入输出 1 解释
号点的两只牛直接躲进 号牛棚,剩下的 只中, 只跑去 号点,还有一只沿 躲进 号点, 号点的 只牛也直接躲进去,这样最慢的牛花费的时间是 。
数据规模与约定
对于 的数据,保证:
- ,。
- ,,。