
小明系列故事——女友的考验
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2024 Accepted Submission(s): 556
Problem Description
终于放寒假了,小明要和女朋友一起去看电影。这天,女朋友想给小明一个考验,在小明正准备出发的时候,女朋友告诉他,她在电影院等他,小明过来的路线必须满足给定的规则:
1、假设小明在的位置是1号点,女朋友在的位置是n号点,则他们之间有n-2个点可以走,小明每次走的时候只能走到比当前所在点编号大的位置;
2、小明来的时候不能按一定的顺序经过某些地方。比如,如果女朋友告诉小明不能经过1 -> 2 -> 3,那么就要求小明来的时候走过的路径不能包含有1 -> 2 -> 3这部分,但是1 -> 3 或者1 -> 2都是可以的,这样的限制路径可能有多条。
这让小明非常头痛,现在他把问题交给了你。
特别说明,如果1 2 3这三个点共线,但是小明是直接从1到3然后再从3继续,那么此种情况是不认为小明经过了2这个点的。
现在,小明即想走最短的路尽快见到女朋友,又不想打破女朋友的规定,你能帮助小明解决这个问题吗?
1、假设小明在的位置是1号点,女朋友在的位置是n号点,则他们之间有n-2个点可以走,小明每次走的时候只能走到比当前所在点编号大的位置;
2、小明来的时候不能按一定的顺序经过某些地方。比如,如果女朋友告诉小明不能经过1 -> 2 -> 3,那么就要求小明来的时候走过的路径不能包含有1 -> 2 -> 3这部分,但是1 -> 3 或者1 -> 2都是可以的,这样的限制路径可能有多条。
这让小明非常头痛,现在他把问题交给了你。
特别说明,如果1 2 3这三个点共线,但是小明是直接从1到3然后再从3继续,那么此种情况是不认为小明经过了2这个点的。
现在,小明即想走最短的路尽快见到女朋友,又不想打破女朋友的规定,你能帮助小明解决这个问题吗?
Input
输入包含多组样例,每组样例首先包含两个整数n和m,其中n代表有n个点,小明在1号点,女朋友在n号点,m代表小明的女朋友有m个要求;
接下来n行每行输入2个整数x 和y(x和y均在int范围),代表这n个点的位置(点的编号从1到n);
再接着是m个要求,每个要求2行,首先一行是一个k,表示这个要求和k个点有关,然后是顺序给出的k个点编号,代表小明不能走k1 -> k2 -> k3 ……-> ki这个顺序的路径;
n 和 m等于0的时候输入结束。
接下来n行每行输入2个整数x 和y(x和y均在int范围),代表这n个点的位置(点的编号从1到n);
再接着是m个要求,每个要求2行,首先一行是一个k,表示这个要求和k个点有关,然后是顺序给出的k个点编号,代表小明不能走k1 -> k2 -> k3 ……-> ki这个顺序的路径;
n 和 m等于0的时候输入结束。
[Technical Specification]
2 <= n <= 50
1 <= m <= 100
2 <= k <= 5
Output
对于每个样例,如果存在满足要求的最短路径,请输出这个最短路径,结果保留两位小数;否则,请输出”Can not be reached!” (引号不用输出)。
Sample Input
3 1
1 1
2 1
3 1
2
1 2
1 1
2 1
3 1
2
1 2
2 1
0 0
1 1
2
1 2
5 3
0 0
5 3
1 2
1 22
5 21
3
1 2 3
2
4 5
2
1 5
0 0
Sample Output
2.00
Can not be reached!
21.65
Can not be reached!
21.65
Source
将女友的要求建ac自动机,然后在树上匹配,f[i][j]表示在i号点对应树上的状态j时候的最短路(从1开始),WA了半天原来是bfs的时候忘记把以失配指针的为结尾的单词状态转移到当前节点上,比如1-2-3-4 ,2-3 , 第一条路径上的'3'显然应该被标记为不能走的路(由于包含了禁路"2-3"),= =还是掌握的不熟练啊。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<stack>
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<time.h>
#include<algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
#define debug puts("debug")
#define LL long long
#define pii pair<int,int>
#define eps 1e-10
double inf=1e20;
int N;
struct Point{
double x,y;
}P[];
double dis(Point A,Point B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double e[][];
struct ach{
int ch[][],fail[],cnt[],tot;
double f[][];
void init(){
tot=;
newnode();
} int newnode(){
memset(ch[tot],-,sizeof(ch[tot]));
fail[tot]=-;
cnt[tot]=;
return tot++;
} void insert(int a[],int n){
int u=;
for(int i=;i<=n;++i){
if(ch[u][a[i]]==-) ch[u][a[i]]=newnode();
u=ch[u][a[i]];
}
cnt[u]=;
}
void getfail(){
queue<int>q;
fail[]=;
for(int i=;i<=N;++i){
if(ch[][i]==-){
ch[][i]=;
}
else{
fail[ch[][i]]=;
q.push(ch[][i]);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
cnt[u]|=cnt[fail[u]];
for(int i=;i<=N;++i){
if(ch[u][i]==-){
ch[u][i]=ch[fail[u]][i];
}
else{
fail[ch[u][i]]=ch[fail[u]][i];
q.push(ch[u][i]);
}
}
}
} void solve(){
for(int i=;i<=N;++i){
for(int j=;j<tot;++j){
f[i][j]=inf;
}
}
f[][ch[][]]=;
for(int i=;i<=N;++i){
for(int j=;j<tot;++j){
if(f[i][j]<inf){
for(int k=i+;k<=N;++k){
if(cnt[ch[j][k]]==){
f[k][ch[j][k]]=min(f[k][ch[j][k]],f[i][j]+e[i][k]);
}
}
}
}
} double ans=inf;
for(int j=;j<tot;++j)
ans=min(ans,f[N][j]);
if(ans==inf) puts("Can not be reached!");
else printf("%.2f\n",ans);
}
}a;
int main()
{
int n,m,i,j,k;
int c[];
while(cin>>n>>m){N=n;
a.init();
if(n==&&m==) break;
for(i=;i<=n;++i) {e[i][i]=;
scanf("%lf%lf",&P[i].x,&P[i].y);
for(j=;j<i;++j){
e[i][j]=e[j][i]=dis(P[i],P[j]);
}
}
for(i=;i<=m;++i){
scanf("%d",&k);
for(j=;j<=k;++j){
scanf("%d",c+j);
}
a.insert(c,k);
} a.getfail();
a.solve();
}
return ;
}