首先我们可以把这个问题视作一个完全图，有一条哈密顿路径的边权是 $1$，其他边权都是 $0$，每次可以询问一条哈密顿路径的边权和。

一个自然的做法是每次随机一个排列并询问，如果得到了 $0$ 就可以确定路径上的所有边都是 $0$ 边，这样一直重复询问直到所有 $0$ 边都被找到。

但是这样太浪费了，因为在后期很有可能出现询问得到的答案恰好等于路径中未知的边数的情况，这时候我们可以确定这些边都是 $1$ 边。

据此我们可以调整一下策略，每次去掉已知的边后如果可以确定剩余的边全为 $0$ 边或全为 $1$ 边，就全部标记，重复该过程直到所有 $0$ 边或所有 $1$ 边都被标记。

写一下发现可以轻松获得 $90$ 分，这意味着我们只要稍微优化一下就过了。

考虑到一次询问如果未知的边太多会导致成功率大大降低，因此我们可以每次随机 $B$ 个排列取一个未知的边数最少的排列进行询问，适当调整 $B$ 的大小可以得到 $95\sim98$ 分。

最后一步最为关键：由于哈密顿路径的特殊性，当一个点已经连接了两条 $1$ 边的时候，我们可以直接将与这个点相连的其他边都标记为 $0$ 边。

加上这个优化后，实测取 $B=100$ 就可以以较高的概率通过了，获得了最短解。