hdu3247 AC自动机+状压dp+spfa

一、题目

题目链接: hdu3247

二、思路和代码 1.思路

也许是做过的最难的一道AC自动机 状压、最短路都搞上了，瘫倒.jpg 要是我会出题了，我要搞个AC自动机+树链剖分 （坏笑 从图论的观点，把每个资源看作一个点的话 可以把这个题理解为TSP问题 参考一位大佬的分析：hdu3247 TSP分析 在此基础上引入距离的定义，spfa挺适合这类图的最短距离求解 dp[i][j]代表状态为i且后缀为[root, j]时的最短长度 这类题就命名为后缀dp吧（叉腰 这样就得到了状态转移方程：

dp[状态记录][后缀j] = min{ dp[状态记录][后缀k] + dis[后缀j][后缀k] }

    for (int i = 0; i