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.