Let me share my method first. My method is very simple. I use the ring as the answer directly. Then this question is similar to a special TSP question.

Firstly, Floyd algorithm is used to preprocess the path length between K special points.

Then the hill climbing algorithm is used to optimize the answer.

The hill climbing algorithm is looking for an arrangement of a_1, a_2... a_k, so that Cost (a_1a_2)+Cost (a_2a_3) +...+ Cost(a_ka_1) is as small as possible.

There are two types of edges in the title, but these two types of edges can be considered as the same edge, which can be reduced to the form of A * day + B .

The final question is how to determine the order of the repaired or constructed paths that have been identified. You can use any method you want. The ranking comparison function I use is A_1*day_2>A_2*day_1.

Finally, my method scored 26131769.

https://www.codechef.com/viewsolution/25241792

If you have some different ideas, please share it, We will be happy.