题目链接
题意
直角坐标系中n个点，限制一些走过的路径的顶点顺序，要求从1到n最短的距离。如：不能经过1 -> 2 -> 3，那么就要求走过的路径不能包含有1 -> 2 -> 3这部分，但是1 -> 3 或者1 -> 2都是可以的，这样的限制路径可能有多条。
思路
求1到n的最短路问题，把所有限制的路建立AC自动机，这里用dp解最短路问题，dp[i][j]表示从1到i的j状态的最短距离。如果tag[trie[j][k]] 为0，则表示不是危险节点，用dp[k][trie[j][k]] = min(dp[k][trie[j][k]], dp[i][j] + mp[i][k])转移。
注意tag[now] |= tag[fail[now]]的步骤，即如果2->3是不能走的，则1->2->3也是不能走的。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const double inf = 1e20;
const int MAXN = 60000 + 10, M = 50;
int trie[MAXN][M];
int tag[MAXN];
int fail[MAXN];
int L = 0, root;
int newnode() {
    for (int i = 0; i < M; i++) trie[L][i] = 0;
    tag[L++] = 0;
    return L - 1;
}
void init() {
    L = 0;
    root = newnode();
}
void insertWords(int a[], int k)
{
    int now = root;
    for (int i = 0; i < k; i++) {
        int next = a[i];
        if(!trie[now][next])
            trie[now][next] = newnode();
        now = trie[now][next];
    }
    tag[now]++;
}
void getFail()//一个节点的fail指针是指向 这个节点表示的字符串的最长后缀串的最后一个节点
{
    queue<int> q;
    for(int i = 0; i < M; i++) {
        if(trie[0][i]) {
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        tag[now] |= tag[fail[now]];
        for (int i = 0; i < M; i++) {
            if(trie[now][i]) {
                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else trie[now][i] = trie[fail[now]][i];
        }
    }
}
struct node {
    double x, y;
}p[55];
int n, m;
double mp[55][55];
double getdis(int i, int j) {
    return sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
}
double dp[55][MAXN];
double solve() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < L; j++)
            dp[i][j] = inf;
    }
    dp[1][trie[0][1]] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < L; j++) {
            if(dp[i][j] < inf) {
                for (int k = i + 1; k <= n; k++) {
                    if(tag[trie[j][k]] == 0)
                    dp[k][trie[j][k]] = min(dp[k][trie[j][k]], dp[i][j] + mp[i][k]);
                }
            }
        }
    }
    double ans = inf;
    for (int i = 0; i < L; i++) {
        ans = min(ans, dp[n][i]);
    }
    return ans;
}
int main()
{
    while (scanf("%d%d", &n, &m), n + m) {
        init();
        for (int i = 1; i <= n; i++) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        for (int i = 1; i <= n; i++) {
            mp[i][i] = 0;
            for (int j = i + 1; j <= n; j++)
                mp[j][i] = mp[i][j] = getdis(i, j);
        }
        int a[10];
        for (int i = 0; i < m; i++) {
            int k;
            scanf("%d", &k);
            for (int j = 0; j < k; j++)
                scanf("%d", &a[j]);
            insertWords(a, k);
        }
        getFail();
        double ans = solve();
        if(fabs(ans - inf) < 1e-3) printf("Can not be reached!\n");
        else printf("%.2f\n", ans);
    }
    return 0;
}