HDU4511 小明系列故事——女友的考验(AC自动机 + DP)

时间:2021-12-15 05:07:30

题目大概说有平面有n个点,从1点出发走到n点,每一步只能走到序号比当前更大的点且走的序列不能包含给定的m个序列中的任何一个,问1走到n的最短路。

用m个序列建个AC自动机,后缀包含整个序列的结点标记一下,然后用dp[u][S]表示走到u点且走的序列的后缀状态是自动机上第S个结点的最短路,这样在AC自动机上跑着转移就OK了。

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define MAXN 666
int tn,ch[MAXN][],fail[MAXN];
bool flag[MAXN];
void insert(int *a,int n){
int x=;
for(int i=; i<n; ++i){
int y=a[i];
if(ch[x][y]==) ch[x][y]=++tn;
x=ch[x][y];
}
flag[x]=;
}
int n;
void getfail(){
memset(fail,,sizeof(fail));
queue<int> que;
for(int i=; i<=n; ++i){
if(ch[][i]) que.push(ch[][i]);
}
while(!que.empty()){
int x=que.front(); que.pop();
for(int i=; i<=n; ++i){
if(ch[x][i]){
que.push(ch[x][i]);
fail[ch[x][i]]=ch[fail[x]][i];
flag[ch[x][i]]|=flag[ch[fail[x]][i]];
}else ch[x][i]=ch[fail[x]][i];
}
}
}
double x[],y[],dist[][],d[][MAXN];
int a[];
int main(){
int m,k;
while(~scanf("%d%d",&n,&m) && (n||m)){
for(int i=; i<=n; ++i){
scanf("%lf%lf",x+i,y+i);
}
tn=;
memset(ch,,sizeof(ch));
memset(flag,,sizeof(flag));
while(m--){
scanf("%d",&k);
for(int i=; i<k; ++i) scanf("%d",a+i);
insert(a,k);
}
getfail();
memset(dist,,sizeof(dist));
for(int i=; i<=n; ++i){
for(int j=i+; j<=n; ++j){
dist[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
}
for(int i=; i<=n; ++i){
for(int j=; j<=tn; ++j) d[i][j]=-;
}
d[][]=;
for(int i=; i<n; ++i){
for(int j=; j<=tn; ++j){
if(d[i][j]<) continue;
if(i== && !flag[ch[][]]){
d[][ch[][]]=;
continue;
}
for(int k=i+; k<=n; ++k){
if(flag[ch[j][k]]) continue;
if(d[k][ch[j][k]]< || d[k][ch[j][k]]>d[i][j]+dist[i][k]) d[k][ch[j][k]]=d[i][j]+dist[i][k];
}
}
}
double res=-;
for(int i=; i<=tn; ++i){
if(d[n][i]<) continue;
if(res< || res>d[n][i]) res=d[n][i];
}
if(res<) puts("Can not be reached!");
else printf("%.2f\n",res);
}
return ;
}