POJ 1699 Best Sequence

AC自动机+spfa最短路
啊啊，明明AC自动机还有最后一题，今晚怕是写不完了，今天写的还有两道没写题解。

最后一道AC自动机与这一题有相似之处，是这一题的强力加强版本。
先把这题给解决了

题意：
给你很多碱基串，不同碱基串在前后缀相同的条件下可以重叠，要你求出最短的碱基串，包含所有给定串。

思路：
AC自动机上状压SPFA，也可考虑TSP的模型。
还是属于比较基础的，连我都可以不看题解写出来的题目。

#include <cstring>
#include <iostream>
#include <queue>
#include <set>

using namespace std;

const int max_n = 250;
const int max_c = 4;
int key[130];

struct Aho {
    int next[max_n][max_c], fail[max_n], end[max_n];
    int root, size;
    queue<int> que;

    int newNode()
    {
        for (int i = 0; i < max_c; i++)
            next[size][i] = 0;
        end[size++] = 0;
        return size - 1;
    }

    inline void init()
    {
        size = 1;
        root = newNode();
    }

    void insert(int id, const string& str)
    {
        int len = str.length(), now = root;
        for (int i = 0; i < len; i++) {
            int c = key[str[i]];
            if (!next[now][c])
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = 1 << id;
    }

    void build()
    {
        fail[root] = root;
        for (int i = 0; i < max_c; i++)
            if (!next[root][i])
                next[root][i] = root;
            else {
                fail[next[root][i]] = root;
                que.push(next[root][i]);
            }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            if (end[fail[now]])
                end[now] |= end[fail[now]];
            for (int i = 0; i < max_c; i++)
                if (!next[now][i])
                    next[now][i] = next[fail[now]][i];
                else {
                    fail[next[now][i]] = next[fail[now]][i];
                    que.push(next[now][i]);
                }
        }
    }

    int dp[max_n][1024];
    bool inq[max_n][1024];
    void solve(int n)
    {
        memset(dp, 0x3f, sizeof dp);
        memset(inq, false, sizeof inq);
        n = 1 << n;
        que.push(root * n);
        dp[root][0] = 0, inq[root][0] = true;
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            int a = cur / n, b = cur % n;
            inq[a][b] = false;
            for (int i = 0; i < max_c; i++) {
                int na = next[a][i], nb = b | end[next[a][i]];
                if (dp[na][nb] > dp[a][b] + 1) {
                    dp[na][nb] = dp[a][b] + 1;
                    if (!inq[na][nb]) {
                        inq[na][nb] = true;
                        que.push(na * n + nb);
                    }
                }
            }
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= size; i++)
            ans = min(ans, dp[i][n - 1]);
        cout << ans << endl;
    }

} aho;

string tmp;
set<string> ks;

int main()
{
    key['A'] = 0, key['C'] = 1, key['T'] = 2, key['G'] = 3;
    ios::sync_with_stdio(false);
    int T, n;
    cin >> T;
    while (T--) {
        ks.clear();
        cin >> n;
        while (n--) {
            cin >> tmp;
            ks.insert(tmp);
        }
        n++;
        aho.init();
        for (set<string>::iterator it = ks.begin(); it != ks.end(); it++)
            aho.insert(n++, *it);
        aho.build();
        aho.solve(n);
    }
    return 0;
}