题目链接 (opens new window)

大意：

$n$ 个顶点的有向图，顶点编号为 $1$ 到 $n$，任意两个不同的顶点 $A,B$，都有一条带权有向边 $A\rightarrow B$。

Masha 想从 $1$ 出发走 $k$ 条边之后返回 $1$，且不走长度为奇数的环。（某一时刻 Masha 在 $v$，之后走了经过奇数条路径后回到 $v$，这是不允许的）

问 Masha 走过的路径权值之和的最小值。

（$n \le 80$，$k\le 10$，边权 $\le 10^8$，保证 k 是偶数）

（不要看位置是 D，这题是除了签到题外最简单的题 qwq 但我还是没做出来）

我首先想到的是广义矩阵乘法，即把矩阵乘法中的乘法换成加法，加法换成最小值（即 $C_{i,j}=\min_{k=1}^n (A_{i,k}+B_{k,j})$），这样邻接矩阵的 $k$ 次方取 $C_{1,1}$ 就是（伪）答案。 但是这个答案是允许奇环的，所以比赛时我接下来就不知道在干嘛了。

第一种思路是先染色，把点分成两部分，不允许走偶数次到达的点（黑点）和不允许走奇数次到达的点（白点），连接黑黑或白白的边权都设成 inf，这样构造的新的矩阵再 $k$ 次方就行了。当时我一算，要至少算 $\binom{79}{4}=1502501$ 次矩阵快速幂，每个矩阵快速幂复杂度 $80^2\times 4=25600$，感觉十分绝望。

这个思路的正解其实是把所有点随机染色成黑白，每跑一遍矩快更新一下答案。事实上染色正确的概率是 $\dfrac 1 {512}$，跑个几千次完全没问题（果然我还没领悟随机化的精髓）。

第二种思路是确定走偶数次到达的点（假设已染黑），这样所有走奇数次到达的点可以随心所欲不逾矩（只要不是黑点就行了），它们两两互不干涉，所以在确定黑点的基础上 for 一下就行了。这样复杂度是 $80^5=3276800000$，不够优化，哭唧唧。

这个思路的正解是事先处理一下所有的 $A\rightarrow C \rightarrow B$ 的权值和存到数组 f[A][B] 中，然后排个序。如果要找 $A$ 经过某一点到 $B$ 的最短路（这个“某一点”不能是黑点），就从 f[A][B] 中找第一个不是黑点的路径。黑点最多也就 5 个，比找 80 次强多了。

（代码？代码是不存在的，作者太懒了）