果然是假了……5n²m+k² 的结论是有问题的，虽然循环节长度是 5n，但是第一个循环之前的长度可能有 25n²，感谢 pink_rabbit 指出。

这样的话最坏情况的复杂度是 25n³m+k²，只是评测数据看上去是随机的没有出现这种情况……果然加强版题目也算 abuse 随机性了（

可以在这里提交加强版题目：https://duck.ac/problem/2003

————————以下原文————————

设 $f(u,v,t)$ 表示 $t$ 天从 $u$ 走到 $v$ 的最大权值（无视美食节），这在 $t$ 足够大时是有循环节的，循环节之间是等差数列，循环节长度不会超过 $5n$。

暴力哈希找到这个循环节，预处理每个 $u$ 出发在循环节之前的部分，即可每次 $O(1)$ 求一个 $f(u,v,t)$。

对于有美食节的情况，可以朴素 $k^2$ 来 DP 是否经过每个地方。总时间是 $5n²m+k²$。

见 https://loj.ac/submission/911370

不知道有没有优美的方法能把这个 $k^2$ 也干掉……