「NOI2020」美食家
图论+矩阵.
暴力DP
略（乱推）
（其实是直接矩阵上手了）
矩阵优化（$O(N^3KlogV)$）
最开始的思路是，要是这道题里的图没有边权就可以矩阵了。于是发现可以拆边：把边权为$z$的边拆成$z$条边，即建出$z-1$个虚拟节点，于是总节点数为$N=n+4m$。
矩阵乘法则定义为$C_{i,j}=max(A_{i,k}+B_{k,j})$，容易证明这样的定义满足结合律。矩阵快速幂即可$O(N^3KlogV)$得到答案。
得分45pts.
进一步优化（$O(N^3KlogV)$）
我们发现可以改拆边为拆点，一个点可以建出$4$个虚拟节点，并将入边拆成这些节点。总点数变成$N=5n$。
得分75pts.
再进一步优化（$O(N^3logV+N^2KlogV)$）
我们的答案矩阵，从第$1$秒滚到第$T$秒，似乎都只用到了第一行（只用考虑从$1$转移出的情况）。于是可以把答案矩阵化简成行向量，预处理快速幂，可做到行向量与矩阵相乘的快乐$O(n^2)$。
于是我们的复杂度变成了$O(N^3logV+N^2KlogV)$。
得分100pts.