CF576D Flights for Regular Customers 题解

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;
}