解题步骤

1. 问题分析 • 小偷需要从节点 1 到节点 N，移动过程中不能与守卫在同一节点或同一条边上 • 守卫按固定路径周期性移动，周期等于其路径长度 • 需计算最短移动时间，或判断无解
2. 核心思路 • 状态表示：使用(当前节点, 当前时间)表示状态 • BFS 搜索：通过广度优先搜索寻找最短时间，保证首次到达节点 N 的时间为最小值 • 冲突检测：对每个潜在移动，检查是否与守卫的位置或路径冲突
3. 关键实现 • 预处理守卫的节点占用和边占用信息（周期 + 偏移量） • 对每个状态考虑两种选择：等待（停留 1 分钟）或移动到相邻节点（耗时 1 分钟） • 冲突检测通过模运算判断时间是否落在守卫的周期内 代码实现 #include <bits/stdc++.h> using namespace std;

typedef long long ll; const ll INF = 1e18;

// 用于存储守卫的周期和禁止时间 struct GuardInfo { int period; int forbidden; };

// 边的表示（用排序的pair确保无向性） using Edge = pair<int, int>; Edge make_edge(int u, int v) { if (u > v) swap(u, v); return {u, v}; }

int main() { ios::sync_with_stdio(false); cin.tie(0);

int N, M;
cin >> N >> M;

// 邻接表
vector<vector<int>> adj(N + 1);
// 边的守卫信息
map<Edge, vector<GuardInfo>> edge_guards;

for (int i = 0; i < M; ++i) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    Edge e = make_edge(u, v);
    edge_guards[e]; // 初始化空向量
}

// 节点的守卫信息
vector<vector<GuardInfo>> node_guards(N + 1);

int K;
cin >> K;
for (int i = 0; i < K; ++i) {
    int l;
    cin >> l;
    vector<int> path(l);
    for (int j = 0; j < l; ++j) {
        cin >> path[j];
    }

    // 记录节点被守卫占据的时间
    for (int t = 0; t < l; ++t) {
        int u = path[t];
        node_guards[u].push_back({l, t});
    }

    // 记录边被守卫经过的时间（t时刻开始经过边）
    for (int t = 0; t < l; ++t) {
        int u = path[t];
        int v = path[(t + 1) % l];
        Edge e = make_edge(u, v);
        if (edge_guards.count(e)) {
            edge_guards[e].push_back({l, t});
        }
    }
}

// BFS：dist[u]表示到达u的最早时间
vector<ll> dist(N + 1, INF);
dist[1] = 0;
queue<pair<int, ll>> q;
q.push({1, 0});

bool found = false;
while (!q.empty()) {
    auto [u, t] = q.front();
    q.pop();

    // 到达终点
    if (u == N) {
        cout << t << endl;
        found = true;
        break;
    }

    // 已找到更优路径，跳过
    if (t > dist[u]) continue;

    // 选项1：等待1分钟
    ll new_t = t + 1;
    bool conflict = false;
    for (auto [p, f] : node_guards[u]) {
        if ((new_t - f) % p == 0) {
            conflict = true;
            break;
        }
    }
    if (!conflict && new_t < dist[u]) {
        dist[u] = new_t;
        q.push({u, new_t});
    }

    // 选项2：移动到相邻节点
    for (int v : adj[u]) {
        Edge e = make_edge(u, v);
        // 检查边在t时刻是否被占用
        bool edge_conflict = false;
        if (edge_guards.count(e)) {
            for (auto [p, f] : edge_guards[e]) {
                if ((t - f) % p == 0) {
                    edge_conflict = true;
                    break;
                }
            }
        }
        if (edge_conflict) continue;

        // 检查目标节点v在new_t时刻是否被占用
        ll new_t_v = t + 1;
        bool node_conflict = false;
        for (auto [p, f] : node_guards[v]) {
            if ((new_t_v - f) % p == 0) {
                node_conflict = true;
                break;
            }
        }
        if (node_conflict) continue;

        // 可以移动
        if (new_t_v < dist[v]) {
            dist[v] = new_t_v;
            q.push({v, new_t_v});
        }
    }
}

if (!found) {
    cout << "impossible" << endl;
}

return 0;

}