[Usaco2015 Open]Bessie
时间限制：10s 空间限制：128MB
题目描述
For Bessie the cow’s birthday, Farmer John has given her free reign over one of his best fields to eat grass.
The field is covered in N patches of grass (1≤N≤1000), conveniently numbered 1…N, that each have a distinct
quality value. If Bessie eats grass of quality Q, she gains Q units of energy. Each patch is connected to up to 10
neighboring patches via bi-directional paths, and it takes Bessie E units of energy to move between adjacent
patches (1≤E≤1,000,000). Bessie can choose to start grazing in any patch she wishes, and she wants to stop
grazing once she has accumulated a maximum amount of energy.
Unfortunately, Bessie is a picky bovine, and once she eats grass of a certain quality, she’ll never eat grass at or
below that quality level again! She is still happy to walk through patches without eating their grass; in fact, she
might find it beneficial to walk through a patch of high-quality grass without eating it, only to return later for a tasty snack.
Please help determine the maximum amount of energy Bessie can accumulate.
为了庆祝贝茜的生日,FJ给她吃草的自由. N块草地,标号1到N(1<=N<=1000),草地有营养价值.当贝茜走到这个草地,可以获得等于这块草地的营养价值的能量. 每块草地最多有10条双向边,每走一条边,贝茜花费E的能量. 贝茜拿可以从任何地方出发,当她不能获得更多的能量的时候她就会停止. 然而因为贝茜挑食,她每次不会吃低于或等于上次的营养价值的草地,所以她获得的能量是严格上升的,当然她可以选择只是经过一块草地而不吃草.
算出贝茜能够获得的最大能量.
输入格式
The first line of input contains N and E. Each of the remaining N lines describe a patch of grass.
They contain two integers Q and D giving the quality of the patch (in the range 1…1,000,000) and
its number of neighbors. The remaining D numbers on the line specify the neighbors.
第一排两个数 N和E
剩下N排,每排包含Q,D两个数字,Q代表这个草地的营养价值,D代表这个点的边数,剩下D个数表示于这块草地相邻的草地.
输出格式
Please output the maximum amount of energy Bessie can accumulate.
一个整数
最大权值
样例输入
5 2 4 1 2 1 3 1 3 4 6 2 2 5 5 2 2 5 2 2 3 4
样例输出
7 Bessie starts at patch 4 gaining 5 units of energy from the grass there. She then takes the path to patch 5 losing 2 units of energy during her travel. She refuses to eat the lower quality grass at patch 5 and travels to patch 3 again losing 2 units of energy. Finally she eats the grass at patch 3 gaining 6 units of energy for a total of 7 energy. Note tha the sample case above is different from test case 1 when you submit.
提示
求译文!请发至lydsy2012@163.com
题目来源
Silver 鸣谢yeguanghao提供译文