#P3380. [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一
[Usaco2004 Open]Cave Cows 1 洞穴里的牛之一
[USACO 2004 Open] Cave Cows 1 洞穴里的牛之一
题目描述
贝茜在一座洞穴中探险。洞穴有 个洞室,编号为 到 ,其中 号是入口。洞室之间有 条双向通道;每条通道连接两个不同的洞室,同一对洞室之间最多有一条通道。
有 个不同的洞室各放着一捆干草。贝茜的体重指数起初为 ,每吃一捆干草就增加 。只有当体重指数不超过一条通道的宽度时,她才能通过该通道。经过有干草的洞室时,她可以选择先不吃。
贝茜从 号洞室出发,最后也必须从 号洞室离开。她最多能吃多少捆干草?
输入格式
从标准输入读入。第一行是三个整数 。接下来 行各给出一个放有干草的洞室编号。随后 行每行三个整数 ,表示洞室 之间的通道宽度为 。
输出格式
向标准输出输出一行一个整数,表示最多吃到的干草捆数。
6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1
4
样例解释
直接通往入口的通道最宽为 ,所以回到入口之前最多能吃 捆。贝茜可沿 行进,在 号洞室各吃一捆,最后在入口再吃一捆。
数据范围与约定
,,,,。