2022-2023 集训队互测 Round 6 - >.<

不能包含某一条路径，这个东西看起来很像字符串啊！我们把这些路径插入到 trie 中，建立 AC 自动机，然后再把 \(n\) 个单点插进去。在建出来的 AC 自动机上跑最短路，钦定某些点不能被进入即可。但是因为字符集是 \(\mathcal O(n)\) 的，所以直接暴力连边复杂度无法接受。

考虑连边的过程，是继承 fail 树父亲的边，再更新它到它在 trie 树上的后继所对应的边。我们就可以发现这个连边其实是可以用可持久化线段树来维护的，支持继承操作和修改操作。这一部分的话时间就是 \(\mathcal O((n+m+L)\log (n+m+L))\) 的了。但是因为边的数量还是很多，所以最短路算法的时间还是难以承受。

既然这些边能在可持久化线段树中用 \(\mathcal O((n+m+L)\log n)\) 个节点存下来，那么为什么要暴力地遍历 \(\mathcal O(n^2)\) 次呢？我们知道，Dijkstra 算法中每次从优先队列中取出的距离是单调不降的。这意味着，某个节点利用可持久化线段树上的一个点上的信息进行松弛对应节点后，下一次另一个节点来松弛时，肯定不会造成任何影响，因为对应的被松弛节点和边权都是固定的，而后面的距离肯定不比前面小，所以后面的松弛是无用的。我们在优先队列中取出一个节点后，遍历这个节点（版本）所对应的可持久化线段树，遇到被标记过的点就退出，再用被遍历到的边松弛，并把这整棵树没有被标记的地方打上标记。那么一条边至多松弛一次，可持久化线段树的每个节点只被遍历一次，故至此我们用 \(\mathcal O((n+m+L)\log (n+m+L))\) 的复杂度解决了此问题。

细节比较多，比如被钦定不能被进入的点要沿 fail 树下传（ACAM 老生常谈的挂法），以及一条边如果在原图中是不存在的，也需要注意不能存在于新图中。