最短路问题-CF1442C Graph Transpositions

发布于 2021-03-14 | 分类于最短路、图论 | 1分钟 | 155字数

最近开了道CF1442C，感觉还是要总结一下最短路类型题的一些特征，这样写的时候能快一点。

个人感觉最短路其实是一种变相的动态规划。无论转移方式整什么花活，套路还是差不多的。我们把二元组 $(位置，路径信息)$ 称为一个状态。对于每一个位置，我们只需要记录下那条最优秀的路径信息即可。这也就是普通的最短路。