这个题还是比较好想的。
首先将所有不可行方案建立AC自动机，然后跑最短路。
首先将小明放在(sta = 0,pos = 0)处，sta表示AC自动机上点的编号，pos表示坐标点的编号。
根据pos枚举下一次可以到达的地方[pos+1,n],然后sta在自动机上移动，如果某一步会使sta位于有标记的节点，那么这一步是不可行。
#include <iostream>#include<time.h>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<string>#include<map>#include<vector>#include <algorithm>#include <queue>#include <cmath>#define LL long long#define ULL unsigned long longusing namespace std;const int MAXS = 55,MAXN = 510;const int MATN = 70;struct MAT{int row,col;ULL mat[MATN][MATN];void Init(int R,int C,int val){row = R,col = C;for(int i = 1;i <= row; ++i)for(int j = 1;j <= col; ++j)mat[i][j] = (i == j ? val : 0);}MAT Multi(MAT c,LL MOD){MAT tmp;tmp.Init(this->row,c.col,0);int i,j,k;for(k = 1;k <= this->col; ++k)for(i = 1;i <= tmp.row; ++i)for(j = 1;j <= tmp.col; ++j)tmp.mat[i][j] += (this->mat[i][k]*c.mat[k][j]);return tmp;}MAT Quick(LL n,LL MOD){MAT res,tmp = *this;res.Init(row,col,1);while(n){if(n&1)res = res.Multi(tmp,MOD);tmp = tmp.Multi(tmp,MOD);n >>= 1;}return res;}void Output(){cout<<"****************"<<endl;int i,j;for(i = 1;i <= row; ++i){for(j = 1;j <= col; ++j)printf("%3lld ",mat[i][j]);puts("");}cout<<"&&&&&&&&&&&&&"<<endl;}};struct Trie{int next[MAXS];int fail;int flag;} st[MAXN];queue<int> q;struct Pos{int x,y;}pos[55];struct ACautomaton{int Top,root;int Creat(){memset(st[Top].next,-1,sizeof(st[Top].next));st[Top].flag = 0;st[Top].fail = -1;return Top++;}void Init(){Top = 0;root = Creat();}inline int CalIndex(int c){return c;}void Insert(int *s){int i = 0,tr = root,tmp;while(s[i] != -1){tmp = CalIndex(s[i]);if(st[tr].next[tmp] == -1)st[tr].next[tmp] = Creat();tr = st[tr].next[tmp],++i;}st[tr].flag = 1;}void GetFail(){st[root].fail = -1;q.push(root);int f,t;while(q.empty() == false){f = q.front();q.pop();for(int i = 0; i < MAXS; ++i){if(st[f].next[i] != -1){t = st[f].fail;while(t != -1 && st[t].next[i] == -1)t = st[t].fail;if(t == -1)st[st[f].next[i]].fail = root;elsest[st[f].next[i]].fail = st[t].next[i];q.push(st[f].next[i]);}}}}int Match(char *s){int i ,tr = root,tmp;int ans = 0;for(i = 0; s[i] != '\0'; ++i){if(s[i] < 'A' || 'Z' < s[i]){tr = root;continue;}tmp = CalIndex(s[i]);while(tr != -1 && st[tr].next[tmp] == -1 )tr = st[tr].fail;if(tr == -1){tr = root;continue;}tr = st[tr].next[tmp];tmp = tr;while(tmp != root && st[tmp].flag != -1){if(st[tmp].flag)ans++,st[tmp].flag = -1;}}return ans;}};int num[10];double dis[510][55];double val[55][55];struct Q{int s,p;};queue<Q> que;double Cal(int P1,int P2){if(P1 == 0 && P2 == 1)return 0;Pos p1 = pos[P1];Pos p2 = pos[P2];return sqrt((p1.x+0.0-p2.x)*(p1.x+0.0-p2.x) + (p1.y+0.0-p2.y)*(p1.y+0.0-p2.y) + 0.0);}int main(){int n,m;int i,k,j;ACautomaton AC;while(scanf("%d %d",&n,&m) && (n||m)){for(i = 1;i <= n; ++i)scanf("%d %d",&pos[i].x,&pos[i].y);AC.Init();while(m–){scanf("%d",&k);for(i = 0;i < k; ++i)scanf("%d",&num[i]);num[k] = -1;AC.Insert(num);}AC.GetFail();for(i = 1;i <= n; ++i){for(j = 1;j <= n; ++j)val[i][j] = sqrt((pos[i].x-pos[i].x)*(pos[i].x-pos[i].x) + (pos[i].y-pos[i].y)*(pos[i].y-pos[i].y));}for(i = 1;i <= n; ++i)val[i][0] = val[0][i] = 0;for(i = 0;i < AC.Top; ++i)for(j = 1;j <= n; ++j)dis[i][j] = -1;dis[0][0] = 0;que.push((Q){0,0});Q f,t;while(que.empty() == false){f = que.front();que.pop();for(i = f.p+1;i <= (f.p == 0 ? 1 : n); ++i){int tr = f.s;while(tr != -1){if(st[tr].next[i] != -1 && st[st[tr].next[i]].flag != 0)break;tr = st[tr].fail;}if(tr != -1)continue;tr = f.s;while(tr != -1){if(st[tr].next[i] != -1)break;tr = st[tr].fail;}if(tr == -1)tr = 0;elsetr = st[tr].next[i];if(dis[tr][i] == -1 || dis[tr][i] > dis[f.s][f.p] + Cal(f.p,i)){dis[tr][i] = dis[f.s][f.p] + Cal(f.p,i);que.push((Q){tr,i});}}}double Min = -1;for(i = 0;i < AC.Top; ++i){if(dis[i][n] != -1){if(Min == -1)Min = dis[i][n];elseMin = min(Min,dis[i][n]);}}if(Min == -1)printf("Can not be reached!\n");elseprintf("%.2lf\n",Min);}return 0;}
，我就想是一只草原中被牧童遗忘的羊，
