Consider the following problem:
There are $n$ points in the plane. Starting from one of them I want to visit each of them once (except the starting node which has to be visited twice) but in a way that minimizes the cost of the total path.
The weight of each edge changes depending on the path followed. For example imagine $n=3$: $A$, $B$, $C$ and we start at $A$. The weight of the edge $xy$ is $Sd_{xy}$, where $d_{xy}$ is the distance between the points $x$ and $y$ and $S$ is a given constant) If I pick the edge $A\to B$, the weight of the edge $B\to A$ is now $(S-s_B)d_{AB}$ because $B$ changes $S$ by a constant amount $s_B$. Similarly if I pick the edge $A\to C$, the weight of the edge $B\to C$ is now $(S-s_C)d_{AC}$ because visiting $C$ changes $S$ by a constant amount $s_C$.
Developing the $n=3$ case, imagine S=11, $d_{AB}=5,d_{AC}=3,d_{BC}=4$ and $s_{A}=2,s_{B}=5,s_{C}=4$. Then there are 4 possible paths:
A->B->C->A with cost $11*5+(11-5)*4+(11-5-4)*3$
(we stop once we reach A because 11-5-4-2=0)
A->B->A->C with cost $11*5+(11-5)*5+(11-4-2)*3$
A->C->B->A with cost $11*3+(11-4)*4+(11-4-5)*5$
A->C->A->B with cost $11*3+(11-4)*3+(11-4-2)*5$
For $n=4$ there will be 3*3!=18 possible paths and so on.
I know that $s_A+s_B+s_C=S$. This generalizes for $n$ points. What is an efficient algorithm for finding the minimum cost path?