翻了翻这题的题解，貌似有两种做法：

• 死了的 SPFA，应该能被卡到 $\mathcal O(nm)$，复杂度应该不正确。

• 在 Dijkstra 上跑 DP，代表。

  我不知道这东西复杂度怎么证，不过状态数的上界是 $\mathcal O(n^2)$，可能能被卡到？

综上，这题是否有复杂度正确的做法？

如果上面两种是对的，求一个证明。