题意：
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!” （引号不用输出）。
#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define st first
#define nd second
#define mp make_pair
#define pii pair<int, int>
#define pdi pair<double, int>
#define gg puts("gg");
//#define local
//#define out1
using namespace std;
const int N = 6e4+;
const int inf = 0x3f3f3f3f;
int id(int c){
return c-;
}
struct Tire{
int nex[N][], fail[N],end[N], ch[N];
int root, L, tot;
int newnode(){
memset(nex[L], -, sizeof(nex[L]));
end[L] = ;
ch[L] = ;
return L++;
}
void init(){
L = tot = ;
root = newnode();
}
void insert(int* s, int len, int tag){
int now = root;
for(int i = ; i < len; i++){
int p = id(s[i]);
if(nex[now][p] == -)
nex[now][p] = newnode();
now = nex[now][p];
ch[now] = p;
}
end[now] = tag;
}
void build(){
queue<int> Q;
fail[root] = root;
for(int i = ; i < ; i++){
int& u = nex[root][i];
if(u == -)
u = root;
else{
fail[u] = root;
Q.push(u);
}
}
while(!Q.empty()){
int now = Q.front();
Q.pop();
for(int i = ; i < ; i++){
int& u = nex[now][i];
if(u == -)
u = nex[ fail[now] ][i];
else{
fail[u] = nex[ fail[now] ][i];
end[u] |= end[ fail[u] ];
Q.push(u);
}
}
}
}
};
Tire ac;
ll x[], y[];
double w[][];
int s[];
vector< pdi > ve[];
priority_queue< pdi, vector< pdi >, greater< pdi > >Q;
double d[];
double dijkstra(int S){
int i, x;
for(i = ; i < ; i++) d[i] = 1e30;
Q.push(mp(d[S]=,S));
while(!Q.empty()){
pdi t = Q.top(); Q.pop();
if(d[x = t.nd] < t.st) continue;
for(i = ; i < ve[x].size(); i++)
if(d[x]+ve[x][i].st < d[ve[x][i].nd]){
d[ve[x][i].nd] = d[x]+ve[x][i].st;
Q.push( mp(d[ve[x][i].nd], ve[x][i].nd) );
}
}
}
int main(){
int n, m, ca = ;
while(~scanf("%d%d", &n, &m), n+m){
for(int i = ; i <= n; i++)
scanf("%lld%lld", x+i, y+i);
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++) w[i][j] = 1e30;
for(int i = ; i <= n; i++)
for(int j = i+; j <= n; j++)
w[i][j] = sqrt( 1.0*(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) ); ac.init();
for(int i = ; i <= n; i++){
s[] = i;
ac.insert(s, , );
} for(int i = ; i <= m; i++){
int k; scanf("%d", &k);
for(int j = ; j < k; j++)
scanf("%d", s+j);
ac.insert(s, k, );
}
ac.build();
for(int i = ; i < ac.L; i++) ve[i].clear();
for(int i = ; i < ac.L; i++){
int u = ac.ch[i]+;
for(int j = u+; j <= n; j++) {
int to = ac.nex[i][id(j)];
if(!ac.end[to]) ve[i].push_back( mp(w[u][j], to) );
}
} dijkstra(ac.nex[][id()]);
double ans = 1e30;
for(int i = ; i < ac.L; i++){
if(ac.ch[i] == id(n))
ans = min(ans, d[i]);
}
if(ans < 1e25)
printf("%.2f\n", ans);
else
puts("Can not be reached!");
}
return ;
}
后记：发现debug能力实在太弱了...调半天没看出来哪错了...代码能力不够啊！！！