OpenJudge

06:Cheney的挖宝之路

总时间限制:
1000ms
内存限制:
16384kB
描述

Cheney最近听说楼兰古城有宝藏挖,他们如愿的到了楼兰并且找到了一张宝藏图,图上写着每个密室的宝藏个数以及没有密室之间的路线,挖宝的规则:

    可以从任何一个密室开始,到任何一个宝藏结束,同时挖完这个密室中的宝藏之后,可以选择它可继续挖的密室之一继续挖,但只能选择一条。

    如挖挖完1密室后,可挖2密室,再挖3,4……,但是不能回头挖,Cheney想得到最多宝石该怎么挖,聪明的你帮帮他吧!

如图最大可得11个宝藏。

输入
first line:
N,M N<=1000,M <= 200.N is value / per room,M is
room path.
second line: is per value.
continue line: is M path.
输出
line: maximum value.
样例输入
3 2
1 1 1
1 2
2 3
样例输出
3
提示
hint: use dynamic programming module.
来源
Cheneychen
全局题号
16500
添加于
2017-12-18
提交次数
1
尝试人数
1
通过人数
1