计数问题，考虑 dp。

设 $f(i,j)$ 表示走到点 $i$，路径长度为 $j$ 时的方案数。状态数 $n^2\times c_i$，显然不行。

考虑优化状态。发现当且仅当 $j\in [\mathrm{dis}_i,\mathrm{dis}_i+k]$ 时有贡献，其中 $\mathrm{dis}_i$ 表示 $1\to i$ 的最短路长度。

此时 $f(i,j)$ 表示走到点 $i$，路径长度为 $\mathrm{dis}_i+j$ 的方案数。状态数 $nk$。

考虑判断无解。当且仅当存在 0 环，且 0 环上的点有合法路径时无解。正反跑一次最短路，把 0 边抽出来跑 tarjan 求 scc，对于每个大小 >1 的 scc 判断即可。

洛谷题解里提到，可以记忆化搜索，过程中判断这个状态是否入栈。然而如果这个状态不提供合法路径，这样判断就是错的。这是我的思考，不知道对不对。

对于剩下的图，显然不能 dijkstra 那样 dp 转移，考虑把状态集合抽象成一个 DAG，拓扑排序跑 dp 即可。但是这样有较多的无效边。感觉跑起来不会快。感觉记忆化搜索会好一些，但也不好说，毕竟拓扑常数小，记忆化搜索需要的栈空间很多，常数非常大。

时间复杂度 $\mathcal O(T(m\log m+nk))$。榜上一些 SPFA 跑得比我 dijkstra 快我是不理解的。应该是那个年代还没有针对 SPFA 构造 hack 数据的习惯。