Posts tagged with SPFA


AC自动机+spfa最短路 啊啊,明明AC自动机还有最后一题,今晚怕是写不完了,今天写的还有两道没写题解。 最后一道AC自动机与这一题有相似之处,是这一题的强力加强版本。 先把这题给解决了 题意: 给你很多碱基串,不同碱基串在前后缀相同的条件下可以重叠,要你求出最短的碱基串,包含所有给定串。 思路: AC自动机上状压SPFA,也可考虑TSP的模型。 还是属于比较基础的,连我都可以不看题解写出来的题目。 #include <cstring> #include <…