Crazy Shopping (ZOJ Problem Set - 3524)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3524

問題

頂点数n、辺数mのDAGが与えられる。DAGの頂点iでは重さtwi、価値tviの商品が無限個買える。ナップサックが重みwまで耐えられる時に商品の価値の合計が最大になるようにする。この時頂点間を移動する際に現在のナップサックの重み*移動距離だけエネルギーを消費する。エネルギーの消費の最小値を求めよ。
1<=n<=600
1<=m<=60000
1<=w<=2000
1<=twi<=w
1<=tvi<=10000

解法

普通にDAGをトポロジカルソートして根の頂点からナップサック問題を解けば、O(wm)な気がするけど、処理が単純だからか間にあうらしい。