hdu4511小明系列故事——女友的考验(ac自动机+最短路）

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 #include<vector>
  7 #include<cmath>
  8 #include<queue>
  9 #include<set>
 10 using namespace std;
 11 #define N 510
 12 #define LL long long
 13 const double eps = 1e-8;
 14 const double pi = acos(-1.0);
 15 const double INF = 1e21;
 16 const int child_num = 51;
 17 double w[55][55];
 18 class AC
 19 {
 20     private:
 21     int ch[N][child_num];
 22     int fail[N];
 23     int val[N];
 24     int id[128];
 25     int Q[N];
 26     double dis[55][N];
 27     int sz;
 28     public:
 29     void init()
 30     {
 31         fail[0] = 0;
 32         for(int i = 0 ; i< child_num ; i++)
 33         id[i] = i;
 34     }
 35     void reset()
 36     {
 37         memset(ch[0],0,sizeof(ch[0]));
 38         memset(val,0,sizeof(val));
 39         sz = 1;
 40     }
 41     void insert(int *a,int k,int key)
 42     {
 43         int i,p=0;
 44         for(i = 1;i <= k; i++)
 45         {
 46             int d = a[i];
 47             if(ch[p][d]==0)
 48             {
 49                 memset(ch[sz],0,sizeof(ch[sz]));
 50                 ch[p][d]= sz++;
 51             }
 52             p = ch[p][d];
 53         }
 54         val[p] = key;
 55     }
 56     void construct()
 57     {
 58         int i,head= 0 ,tail = 0;
 59         for(i = 1 ;i < child_num ; i++)
 60         {
 61             if(ch[0][i])
 62             {
 63                 fail[ch[0][i]] = 0;
 64                 Q[tail++] = ch[0][i];
 65             }
 66         }
 67         while(head!=tail)
 68         {
 69             int u = Q[head++];
 70             val[u]|=val[fail[u]];
 71             for(i = 1; i < child_num ; i++)
 72             {
 73                 if(ch[u][i])
 74                 {
 75                     fail[ch[u][i]] = ch[fail[u]][i];
 76                     Q[tail++] = ch[u][i];
 77                 }
 78                 else ch[u][i] = ch[fail[u]][i];
 79             }
 80         }
 81     }
 82     void work(int n)
 83     {
 84         int i,j,g;
 85         for(i = 1; i <= n ;i++)
 86         for(j = 0 ; j <= sz ;j++)
 87         dis[i][j] = INF;
 88         if(val[1])
 89         {
 90             puts("Can not be reached!");
 91             return ;
 92         }
 93         dis[1][ch[0][1]] = 0;
 94         for(i = 1 ; i <= n ;i++)
 95         {
 96             for(j = 0; j < sz ;j++)
 97             {
 98                 for(g = 1; g <= n ;g++)
 99                 {
100                     int np = ch[j][g];
101                     if(val[np]) continue;
102                     dis[g][np] = min(dis[g][np],dis[i][j]+w[i][g]);
103                 }
104             }
105         }
106         double ans = INF;
107         for(i = 0 ; i < sz ; i++)
108         {
109             ans = min(ans,dis[n][i]);
110         }
111         if(fabs(ans-INF)<eps) puts("Can not be reached!");
112         else
113         printf("%.2f\n",ans);
114     }
115 }ac;
116 struct node
117 {
118     double x,y;
119 }pp[55];
120 double cdis(node a,node b)
121 {
122     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
123 }
124 int a[10];
125 int main()
126 {
127     int n,m,k,i,j;
128     ac.init();
129     while(scanf("%d%d",&n,&m)&&n&&m)
130     {
131         ac.reset();
132         for(i = 1 ;i <= n; i++)
133         {
134             scanf("%lf%lf",&pp[i].x,&pp[i].y);
135         }
136         for(i = 1; i <= n ;i++)
137             for(j = 1; j <= n ;j++)
138             w[i][j] = cdis(pp[i],pp[j]);
139         for(i = 1; i <= m ; i++)
140         {
141             scanf("%d",&k);
142             for(j= 1 ;j <= k; j++)
143             scanf("%d",&a[j]);
144             ac.insert(a,k,1);
145         }
146         ac.construct();
147         ac.work(n);
148     }
149     return 0;
150 }