一、题目

题目链接: 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