题目大概说有平面有n个点，从1点出发走到n点，每一步只能走到序号比当前更大的点且走的序列不能包含给定的m个序列中的任何一个，问1走到n的最短路。
用m个序列建个AC自动机，后缀包含整个序列的结点标记一下，然后用dp[u][S]表示走到u点且走的序列的后缀状态是自动机上第S个结点的最短路，这样在AC自动机上跑着转移就OK了。
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<queue>
5 #include<algorithm>
6 using namespace std;
7 #define MAXN 666
8 int tn,ch[MAXN][55],fail[MAXN];
9 bool flag[MAXN];
10 void insert(int *a,int n){
11 int x=0;
12 for(int i=0; i<n; ++i){
13 int y=a[i];
14 if(ch[x][y]==0) ch[x][y]=++tn;
15 x=ch[x][y];
16 }
17 flag[x]=1;
18 }
19 int n;
20 void getfail(){
21 memset(fail,0,sizeof(fail));
22 queue<int> que;
23 for(int i=1; i<=n; ++i){
24 if(ch[0][i]) que.push(ch[0][i]);
25 }
26 while(!que.empty()){
27 int x=que.front(); que.pop();
28 for(int i=1; i<=n; ++i){
29 if(ch[x][i]){
30 que.push(ch[x][i]);
31 fail[ch[x][i]]=ch[fail[x]][i];
32 flag[ch[x][i]]|=flag[ch[fail[x]][i]];
33 }else ch[x][i]=ch[fail[x]][i];
34 }
35 }
36 }
37 double x[55],y[55],dist[55][55],d[55][MAXN];
38 int a[6];
39 int main(){
40 int m,k;
41 while(~scanf("%d%d",&n,&m) && (n||m)){
42 for(int i=1; i<=n; ++i){
43 scanf("%lf%lf",x+i,y+i);
44 }
45 tn=0;
46 memset(ch,0,sizeof(ch));
47 memset(flag,0,sizeof(flag));
48 while(m--){
49 scanf("%d",&k);
50 for(int i=0; i<k; ++i) scanf("%d",a+i);
51 insert(a,k);
52 }
53 getfail();
54 memset(dist,0,sizeof(dist));
55 for(int i=1; i<=n; ++i){
56 for(int j=i+1; j<=n; ++j){
57 dist[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
58 }
59 }
60 for(int i=1; i<=n; ++i){
61 for(int j=0; j<=tn; ++j) d[i][j]=-1;
62 }
63 d[0][0]=0;
64 for(int i=0; i<n; ++i){
65 for(int j=0; j<=tn; ++j){
66 if(d[i][j]<0) continue;
67 if(i==0 && !flag[ch[0][1]]){
68 d[1][ch[0][1]]=0;
69 continue;
70 }
71 for(int k=i+1; k<=n; ++k){
72 if(flag[ch[j][k]]) continue;
73 if(d[k][ch[j][k]]<0 || d[k][ch[j][k]]>d[i][j]+dist[i][k]) d[k][ch[j][k]]=d[i][j]+dist[i][k];
74 }
75 }
76 }
77 double res=-1;
78 for(int i=0; i<=tn; ++i){
79 if(d[n][i]<0) continue;
80 if(res<0 || res>d[n][i]) res=d[n][i];
81 }
82 if(res<0) puts("Can not be reached!");
83 else printf("%.2f
",res);
84 }
85 return 0;
86 }