First, if we can find the vertex-set restricted minimum path(endpoint value included) in a graph in \(O(f(n))\), then we can solve the original problem in \(O(nf(n))\). Here’s how it works:

• Enumerate the 3-degree vertex \(x\) in the Q(the not-forming-cycle edge’s endpoint which is in the cycle).
• Find the minimum path in the graph without \(x\).Let the vertex value of a vertex \(v\) neighbouring \(x\) be \(E(v,x)\) . Let the two vertices \(v_1,v_2\) be neighbouring \(x\) in the cycle. Let \(E(v_1,x)=w_1,E(v_2,x)=w_2\), where \(E(u,v)\) is the weight of the edge between \(u\) and \(v\). Let \(w\) be the weight of the path(endpoint value included).
• Update the answer with \(w+\min\limits_{(u,x)\in E,u\neq v_1,u\neq v_2}E(u,x)\).
• Find the minimum path in the graph without \(x\) and \(v_1\). Let \(w_1\) be the weight of the path(endpoint value included). Update the answer with \(E(x,v_1)+w_1\).
• Do the same with \(v_2\).

The answer is the minimum value of an update. Why is it correct?

The only problem is that the graph is like a \(\theta\) instead of a \(Q\). But it’s obvious that \(\theta\) is not optimal!

Now consider how to find the minimum path, where

• Its endpoint is restricted in a set.
• Its value is the sum of values of edges plus the sum of values of its two endpoints.

It is very similar to a shortest-path problem, which can be solved in \(O(N^2+M)\) by Dijkstra’s algorithm. But it has many endpoints. If we do it naively, we may find a path where there is only one vertex. But we need to find a path with different endpoints!

We know, for two different natural numbers, there must be at least one bit that one differs from the other. We can enumerate the bit and begin with the vertices whose index has the bit \(0\) and end with the vertices whose index has the bit \(1\). Problem solved!

If you are still confused about it, please refer to the submission.