Fukuoka 2011 F - City Merger <路径压缩,位运算,AC自动机>

本题求用最短的长度字符串包含所给子串...由于存在多串匹配的问题...容易联想到AC自动机...
最多14个city..用14位的二进制数表示已经在串中否...对多串构造Trie树..进一步构造好AC自动机...可以用dp [ k ] [ i ] [ x ] 来表示长度为k的串..末字符落在trie树的i处..包含14个关系的x...但这样的复杂度..以最坏的考虑..会有240*240*16384=943718400=9*10^8...无法接受...
那么此时就要压缩路径了..由于Trie树中有很多无法产生更新的点...没必要dp时一次又一次的路过...所以将Trie树中x非0的点找出来...从每个点开始BFS...做出到其他有效点的最短距离...这样大大优化了dp过程...

Program:
[cpp]
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<stack>
#include<math.h>
#include<map>
#define oo 1000000000
using namespace std;
struct node
{
    int fail,son[26],city,w;
}point[1001];
struct node2
{
    int len,x;
};
int n,m,k,g,arc[303][303],need[303],l[303],dp[2][303][18000];
char s[30];
queue<int> myqueue;
void Built_Trie()
{
       int len,i,j,k,h,x;
       memset(point,0,sizeof(point));
       m=0; g=1;
       for (k=0;k<n;k++)
       {
             scanf("%s",s);
             len=strlen(s);
             h=0;
             for (i=0;i<len;i++)
             {
                    x=s[i]-'A';
                    if (!point[h].son[x]) point[h].son[x]=++m;
                    h=point[h].son[x];
             }
             point[h].w|=g;
             g*=2;
       }
       g--;
       return;
}
void Built_AC_Automation()
{
       int i,h,k;
       while (!myqueue.empty()) myqueue.pop();
       for (i=0;i<26;i++)
          if (point[0].son[i]) myqueue.push(point[0].son[i]);
       while (!myqueue.empty())
       {
               h=myqueue.front();
               myqueue.pop();
               point[h].w|=point[point[h].fail].w;
               for (i=0;i<26;i++)
               {
                     k=point[h].fail;
                     while (!point[k].son[i] && k) k=point[k].fail;
                     point[point[h].son[i]].fail=point[k].son[i];
                     if (!point[h].son[i])
                          point[h].son[i]=point[k].son[i];
                      else
                          myqueue.push(point[h].son[i]);
               }
       }
       return;
}
void Built_Arc()
{
       int i,k,h,len[303];
       memset(arc,-1,sizeof(arc));
       n=0;
       for (k=0;k<=m;k++)
          if (point[k].w)
          {
                need[n++]=k;
                point[k].city=n;
          }
       need[n]=0;
       for (k=0;k<=n;k++)
       {
              h=need[k];
              memset(len,-1,sizeof(len));
              myqueue.push(h);
              len[h]=0;
              while (!myqueue.empty())
              {
                    h=myqueue.front();
                    myqueue.pop();
                    i=h;
        &

补充：软件开发 , C++ ,