This is not a programming competition problem. This is a paraphrase of a problem I am trying to solve at my job.
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
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
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.
At some arbitrary moment, let's assume we are at
nodeA and the value of
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
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
amtA and when we reach
nodeB our amount becomes
amtB = (amtA-weightAB). If we want to go to
nodeC, the weight will be
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.