Visits: 282

CF576D Flights for Regular Customers

题意

• 给定一张 $n$ 个点 $m$ 条边的有向图。
• 一开始你在 $1$ 号节点，你要走到 $n$ 号节点去。
• 只有当你已经走过了至少 $d_i$ 条边时，你才能走第 $i$ 条边。
• 问最少要走多少条边，或判断无法到达。
• $n,m \le 150$，$d_i \le 10^9$。

题解

首先对边排序，然后从小到大依次加入每条边。

考虑只有当前存在的边时，答案怎么求。

假设此时加入的边的 $d$ 值为 $t$，首先要求的是经过恰好 $t$ 条边时可以到达哪些点。

这个可以从加入上一条边时的答案递推过来，这个递推式可以矩阵加速。

求出恰好 $t$ 条边时可以到达哪些点后，对整个图进行一次 bfs 即可求出当前的答案。

这样时间复杂度是 $\mathcal O(n^3m \log d)$ 的，无法通过。

注意到每个点的状态只有 $0/1$ 两种，分别对应着无法到达和可以到达。

因此可以 bitset 优化，时间复杂度 $\mathcal O(\frac{n^3m \log d}w)$。

代码

const int N = 150;
const ll inf = 1e18;
int n, m;
struct E {
    int x, y, z;
    inline void input() { rd(x), rd(y), rd(z), --x, --y; }
    inline friend bool operator < (E a, E b) { return a.z < b.z; }
} e[N];
ll d[N], ans;
#define bt bitset<N>
bt v;
struct mt {
    bt a[N];
    inline friend bt operator * (bt x, mt y) {
        bt z;
        for (int i = 0; i < n; i++) z[i] = (x & y.a[i]).any();
        return z;
    }
    inline friend mt operator * (mt x, mt y) {
        mt z;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (x.a[i][j]) z.a[i] |= y.a[j];
        return z;
    }
} a;

inline void ksm(mt x, int y, bt &z) {
    while (y) {
        if (y & 1) z = z * x;
        x = x * x, y >>= 1;
    }
}

int main() {
    rd(n), rd(m);
    for (int i = 0; i < m; i++) e[i].input();
    sort(e, e + m);
    v[0] = 1;
    ans = inf;
    for (int i = 0, t = 0; i < m; i++) {
        if (e[i].z >= ans) break;
        int o = e[i].z - t;
        ksm(a, o, v);
        a.a[e[i].y][e[i].x] = 1;
        t = e[i].z;
        queue<int> q;
        for (int x = 0; x < n; x++)
            if (v[x]) q.push(x), d[x] = 0;
            else d[x] = inf;
        while (q.size()) {
            int x = q.front();
            q.pop();
            for (int y = 0; y < n; y++)
                if (a.a[y][x] && d[y] == inf)
                    d[y] = d[x] + 1, q.push(y);
        }
        ans = min(ans, t + d[n-1]);
    }
    if (ans == inf) prints("Impossible");
    else print(ans);
    return 0;
}