假期计划

由于要考虑相邻城市之间的中转点不超过 \(k\)（即所经过边数不超过 \(k+1\)），所以首先要预处理出 \(dis[i][j]\)，即两两之间的点的距离，可以 bfs \(n\) 次解决。然后就是考虑怎么进行枚举了。首先如果直接枚举四个点显然不可行，时间复杂度是 \(O(n^4)\)，应该想到一个技巧：折半枚举。假设点依次是 \(1->A->B->C->D->1\)，可以先考虑弄 \(1->A->B\)，再弄 \(1->C->D\)，然后想办法拼接起来。

接下来是重点：对于每个点，都记录一个从 \(1\) 到某个中间点再到它的贡献，然后取贡献前三名的中间点。然后枚举 \(B，D\) 两点，取它们存储的中转点 \(A,C\) 进行两两组合，应该有 \(3\times 3=9\) 种情况。

这个做法的确很好，但为什么取贡献前三名的点呢？

假如留一个，万一 \(B,D\) 的 \(A,C\) 相等，显然不合法。

假如留两个，如下图

上图中，无论 \(A,C\) 怎么组合，都会只有 \(2\sim 3\) 个不同的点。

留三个，如下图

就算有 \(B,C\)，其他的都相同，也可以构造出 \(1->E->B->F->D->1\)。上述的是最坏情况，如果二者其他不相同，那么更加可行了。

思路还是有点难想的，就当作刷新一下自己的认知。