首先考虑一个暴力的做法，暴力建图，对每一个询问跑BFS，总复杂度\(O(n^2q)\)，不可过
我们发现这个图的瓶颈在于对于光标的跳转(即第三种操作)，我们可以建一个虚拟节点来解决这个问题，原图的点数变为\(O(n+D^2)\)，边数\(O(n)\)，其中\(D\)表示字母种类数
这时我们把原题的复杂度优化成了\(O(nq)\)，但还是不可过
我们发现一个问题，虚拟节点的个数很少，且对于一个询问，如果最优路径不经过任何一个虚拟节点，我们可以直接\(O(1)\)的计算他们的距离
而如果其最优路径经过了若干个虚拟节点，我们可以枚举经过的虚拟节点之一是什么，计算出\(s \rightarrow f\)和\(s \rightarrow t\)的距离，这里可以直接使用01bfs解决
我们这么分情况讨论的优点是我们只枚举了\(O(D^2)\)个虚拟节点，所以总复杂度\(O(nD^2+qD^2)\)
标签：原题,复杂度,我们,CF1860E,虚拟,节点,rightarrow From： https://www.cnblogs.com/fox-konata/p/17642011.html