Reformulation


We have a graph G with 1000 nodes and 2000 edges. Each node n has a value v_n
and we want to find a path n1... nk such that Σ v_{n_j} - Ck² is maximal and
nk=n1=1


===

[Simplification] lets us suppose we know the length L of the resulting path.


We can ask q(n,L) what is the max Σv_{ni} for a path n1 ... nL
starting from n1=n and ending in nL=1.

q(n,0) = -∞ when n≠1 and 0 otherwise

q(n,L) = max_{n→n'} v_n+q(n',L-1)


The complete problem becomes min_L q(1,L) - C×L² and we can see that
L≤1000 therefore it is OK in total time as there are L×N states and
the total number of transitions is L×M.

====