题解 CF576D 【Flights for Regular Customers】
xht
2019-12-04 23:30:17
> [CF576D Flights for Regular Customers](https://codeforc.es/contest/576/problem/D)
## 题意
- 给定一张 $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)$。
## 代码
```cpp
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;
}
```