[NOI2020] 美食家

对图的邻接矩阵应用矩阵乘法，限制路径上的边数做计数/最优化时，相当于每条边的边权为 $1$。但此时图具有边权，所以考虑把每条边拆成一条长为边权的链。这样点最多有 $(w-1)m+n$ 个，无法接受。于是我们考虑把从同一个点出发的边拆成的链进行合并。具体地，从每个点 $u$ 引出一条长为 $w$ 的链，然后从链上相应的节点连向 $u$ 的后继 $v$。

邻接矩阵做矩阵乘法需要记录边权，而此题需要对点权求最值。所以将每条边的边权定义为终点的点权，节点 $1$ 的点权单独统计。

美食节的处理看作点权修改，也即边权修改，快速幂过程中对于具有修改的时刻进行特殊处理即可。