题解
可以发现，对于巡演的路线 \(x\to y\) 和 \(a\to b\)，若 \(\min(x,y)\neq \min(a,b)\) 或 \(\max(x,y)\neq \max(a,b)\)，则其答案互不影响。不妨设 \(x，我们需要对每一种 \((x,y),(y,x)\) 求出最小值。
将巡演路线中 \(x\to y\) 记作 \((\)，\(y\to x\) 记作 \()\)，则它形成了一个仅由左右括号组成的序列。设 \(A\) 为 \(x\to y\) 的最优价钱，\(B\) 同理；\(AB\) 为 \(x\to y\to x\) 的最优价钱，\(BA\) 同理。则有：\(A=\min(\operatorname{cost}(x\to y),AB),AB=\min(A+B,\operatorname{cost}(x\to y\to x))\)，\(B,BA\) 同理。
不妨设 \(AB，于是，最优策略是：不断地删去括号序列中的 \(()\) 子序列（不必连续），然后不断地删去 \()(\) 子序列，直到只剩下若干 \((\) 或 \()\)。
若 \(AB>BA\)，则只需要将所有左、右括号调换，然后 \(A,B\) 调换，\(AB,BA\) 调换，再执行上面的策略即可。
注意 \(\max(AB,BA)\) 可能会达到 \(2\times 10^9\)，因此 \(\inf\) 要开得大一点。
代码
#include
#include
#include
#include
#include
#include