题解归档 - cf104118E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104118E
• 本地来源：problems/cf104118E/idea.md
• 题目链接：https://codeforces.com/gym/104118/problem/E
• 原始标题：Gym 104118E - Escape from Markov

思路

Gym 104118E - Escape from Markov

All patrol plans have the same period l. During integer hour [t,t+1), a road is unusable iff some patrol car traverses that undirected road at phase t mod l.

Do not expand n*l states. Waiting is allowed at any city, so Dijkstra on cities is enough:

• for every edge, collect the blocked phases;
• when relaxing an edge from time d, compute the smallest wait w >= 0 such that phase (d+w) mod l is not blocked for that edge;
• transition cost is w + 1.

The total number of patrol phases is p*l <= 1e6, so we can preprocess each edge's blocked phases. For each blocked phase store how long one must wait until the next unblocked phase; queries are binary searches in that edge's table.

Complexity: O((m + p*l) log m + m log n).

Checks:

• official sample 1
• statement samples 2-4 reconstructed from PDF
• randomized brute force against full (city, phase) BFS for small graphs

代码

来源：problems/cf104118E/solution.cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static inline long long edge_key(int u, int v) {
    if (u > v) swap(u, v);
    return (1LL * u << 32) | (unsigned int)v;
}

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

    int n, m, p, len;
    cin >> n >> m >> p >> len;

    vector<vector<pair<int, int>>> g(n + 1);
    unordered_map<long long, int> id_of;
    id_of.reserve((size_t)m * 2);
    id_of.max_load_factor(0.7);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
        id_of[edge_key(u, v)] = i;
    }

    vector<vector<int>> blocked(m);
    vector<int> path(len);
    for (int car = 0; car < p; ++car) {
        for (int i = 0; i < len; ++i) cin >> path[i];
        for (int i = 0; i < len; ++i) {
            int u = path[i], v = path[(i + 1) % len];
            auto it = id_of.find(edge_key(u, v));
            if (it != id_of.end()) blocked[it->second].push_back(i);
        }
    }

    int src, dst;
    cin >> src >> dst;

    vector<vector<pair<int, int>>> wait_table(m);
    vector<char> always_blocked(m, 0);

    for (int e = 0; e < m; ++e) {
        auto &v = blocked[e];
        if (v.empty()) continue;
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        if ((int)v.size() == len) {
            always_blocked[e] = 1;
            continue;
        }

        vector<pair<int, int>> table;
        table.reserve(v.size());
        int sz = (int)v.size();
        int i = 0;
        while (i < sz) {
            int j = i;
            while (j + 1 < sz && v[j + 1] == v[j] + 1) ++j;
            for (int t = i; t <= j; ++t) table.push_back({v[t], v[j] - v[t] + 1});
            i = j + 1;
        }

        if (v.front() == 0 && v.back() == len - 1 && table.size() == v.size()) {
            int first_end = 0;
            while (first_end + 1 < sz && v[first_end + 1] == v[first_end] + 1) ++first_end;
            int last_start = sz - 1;
            while (last_start - 1 >= 0 && v[last_start - 1] + 1 == v[last_start]) --last_start;
            int low_end = v[first_end];
            for (auto &[phase, wait] : table) {
                if (phase >= v[last_start]) wait = (len - phase) + low_end + 1;
            }
        }

        sort(table.begin(), table.end());
        wait_table[e].swap(table);
    }

    auto wait_for = [&](int e, int phase) -> int {
        if (always_blocked[e]) return -1;
        auto &tab = wait_table[e];
        if (tab.empty()) return 0;
        auto it = lower_bound(tab.begin(), tab.end(), pair<int, int>{phase, -1});
        if (it != tab.end() && it->first == phase) return it->second;
        return 0;
    };

    const ll INF = (1LL << 62);
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        if (u == dst) break;
        int phase = (int)(d % len);
        for (auto [to, eid] : g[u]) {
            int w = wait_for(eid, phase);
            if (w < 0) continue;
            ll nd = d + w + 1;
            if (nd < dist[to]) {
                dist[to] = nd;
                pq.push({nd, to});
            }
        }
    }

    if (dist[dst] == INF) cout << "IMPOSSIBLE\n";
    else cout << dist[dst] << '\n';
    return 0;
}