This is not a programming competition problem. This is a paraphrase of a problem I am trying to solve at my job.

A graph `G`

consists of `N`

nodes where every node has some positive value. Graph `G`

is a connected, dense graph where edges are bi-directional and the number of edges can go up to `O(N^2)`

.

To traverse an edge we have to pay a tax equal to the edge's weight. The weight of an edge depends on its two node's values. If the value of two connected nodes is `vA`

and `vB`

, `calc_weight(vA, vB)`

returns the weight of the edge. Please refer to the clarification section to understand why we can not pre-calculate all the weights.

We start with some initial value (let's call it amount). From a *predefined* source node, our goal is to reach the *predefined* destination node, with minimum tax paying. Both the source and destination are present in the graph.

#### Clarification:

At some arbitrary moment, let's assume we are at `nodeA`

and the value of `nodeA`

is `valA`

. And at that moment our amount is `amtA`

. Let's consider `nodeB`

has a bi-directional edge from `nodeA`

. If we want to go `nodeA`

-> `nodeB`

, we first have to calculate the edge's weight.

The catch is when we are at a node, we have to call `weightAB = calc_weight(amtA+valA, valB)`

. See how our presence affects the parameters of the function.

we then pay `weightAB`

from `amtA`

and when we reach `nodeB`

our amount becomes `amtB = (amtA-weightAB)`

. If we want to go to `nodeB`

-> `nodeC`

, the weight will be `calc_weight(amtB+valB, valC)`

.

I can solve this problem using a bitmaskDP. But `N`

can reach up to 2000.

Thanks in advance for any ideas/suggestions. Also if you have seen any problem that closely resembles this, please point me in that direction.