Use C++ to do it. Thanks

Given you start with a future expiration, find the minimal cost combination of available trades to turn your start position into your end position.

Definition of Future: An agreement to buy or sell an asset at a fixed price but to be delivered and paid for at some later date (the expiration date).

Definition of Roll: The process of closing out positions in soon-to-expire contracts in favor of contracts with later expiration dates.

Example 1

Given I start with a January Future Contract And my target is the February Future Contract And the (January,February) Contract costs -1 When I sell the (+Jan-Feb) Contract Then I sell a January Contract and buy a February Contract for a loss of 1 And I now own the Feb Future Contract for a loss of 1 

Example 2

Given I start with a January Future Contract And my target is the March Future Contract And the (January,February) Contract costs -1 And the (January,March) Contract costs -4 And the (February,March) Contract costs -2 When I sell the (+Jan-Feb) Contract And I sell the (+Feb-Mar) Contract Then I sell a January Contract and buy a February Contract for a loss of 1 Then I sell a February Contract and buy a March Contract for a loss of 2 And I now own the Feb Future Contract for a loss of 3 

In example 2, selling the Jan,Mar combination costs more (4) than the cost of selling both the Jan,Feb and Feb,Mar combinations.

Your goal is to find the optimal combination of assets to complete the roll as quick as possible for the best price. The optimal solution will output the roll combination with the minumum cost in the most efficient way possible. If two combinations of assets have the same minimum cost, choose the one with the least trades

Input:

The input gives you your starting and ending months for the roll and all future combinations and their costs. The future combinations contain two expiration months and a cost. When you buy the future combination, you buy the first month and sell the second month and pay the cost. When you sell the future combination, you sell the first month and buy the second month and earn the cost.

Input: Start,End Month,Month,Cost;Month,Month,Cost;...

For Example 2, the input would be...

Jan,Mar Jan,Feb,-1;Jan,Mar,-4;Feb,Mar,-2 

Output:

The output should show the future combinations that result in the minimal cost between the start and end future months. You should output the future trades in the order you traded them to get to the roll month.

Output: +(Month,Month) -(Month,Month) Total Minimum Cost

For Example 2, the output would be...

-(Jan,Feb) -(Feb,Mar) 3 

Test 1

Test Input

Download Test Input

Jan,Apr Jan,Feb,-2;Jan,Mar,-2;Jan,Apr,-4;Feb,Mar,-2;Feb,Apr,-1;Mar,Apr,-3 

Expected Output

Download Test Output

-(Jan,Mar) +(Feb,Mar) -(Feb,Apr) 1 

Test 2

Test Input

Download Test Input

Jan,Mar Jan,Feb,-3;Jan,Mar,-7;Feb,Mar,-3 

Expected Output

Download Test Output

-(Jan,Feb) -(Feb,Mar) 6 

Test 3

Test Input

Download Test Input

Jan,Mar Jan,Feb,-3;Jan,Mar,-6;Feb,Mar,-3 

Expected Output

Download Test Output

-(Jan,Mar) 6 

Test 4

Test Input

Download Test Input

Jan,Feb Jan,Feb,-3 

Expected Output

Download Test Output

-(Jan,Feb) 3