题目解析 状态压缩动态规划 定义 dp[i][mask][j]dp[i][mask][j]dp[i][mask][j] 为第 iii 位朋友，已经经过的站点集合为 maskmaskmask，此时位于车站 jjj 的可行性。 那么我们就可以对每一位朋友分开考虑，并使用状态压缩动态规划，在 O(KN22N)\mathrm{O}(KN^22^N)O(KN22N) 的时间复杂度内，计算出上述 DPDPDP 数组。 然后我们定义 turn[step][i]turn[step][i]turn[step][i] 表示，经过 stepstepstep 次移动，位于车站 iii 的朋友的集合。根据已经得出的 dpdpdp 数组，我们可以很容易计算出 turnturnturn 数组。 最后根据 turn[step][i]turn[step][i]turn[step][i] 中的存储的集合是否为所有朋友的全集，来判断，是否可以在站点 iii 汇合即可。 AC代码

一开始没读题就0帧起手，写了个bfs找环+Floyd算法. 直到我看到了：不会重复经过同一个车站. 天塌了70+行的代码白写了 但是这个提示也带给我了一个好消息：消耗的时间最多也不会超过 151515. 这就让我想到了最短Hamilton路径的解法：状压DP. 巧了，在这题也同样适用！ 我们弄个dp，dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示从 iii 出发，第 kkk 个状态，最后一个点为 jjj 是否可能实现. 然后枚举每个时间和所有点，判断当时间为 iii，选取 jjj 点作为车站是否可行. 时间复杂度：O(2N×N3)O(2^N\times N^3)O(2N×N3).