夏晓光(loveJY)的博客

IOI2020集训队作业

小清新的一道题,因为不需要灵机一动

所以$Orzhq$

题意翻译

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

看完题我们一定会对n,m比较小感到诧异

因为这样子至少走过$d_i$条边这个限制就会变得鸡肋,我们可以矩阵快速幂啊!

那么做法也就呼之欲出了

我们把原来的边按照$d_i$拍下序,然后从小到大处理

然后考虑枚举每条边,然后把它加入原来的矩阵中,然后用快速幂让这个矩阵自己乘自己乘$d_{i+1}-d_i$次

再依次这样做,可以判断能否到达

如果要看最少走多少条边我们可以考虑如果两个相邻的$d_i$值小于n就暴力做一下,否则就先做n次看能不能到达,之后再快速幂做$d_i+1-d_i-n$次,因为剩下的一定也不会使他们到达了

发现每个点要么是0要么是1,就可以用bitset来写矩阵乘法,复杂度$/\omega$,否则过不去

code:

//From Dawn light
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using std::sort;
using std::bitset;
int n, m;
bitset<160>a[160], b[160], T[160];
struct rec {
	int from, to, w;
	bool operator<(const rec &x)const {
		return w < x.w;
	}
} edge[160];

void times(bitset<160> *a, bitset<160> *b) {
	bitset<160> res[160];
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
			if(a[i][j])res[i] |= b[j];
		}
	}
	for(int i = 1; i <= n; ++i)a[i] = res[i];
}

inline void ksm(bitset<160> *a, int b) {
	bitset<160> res[160];
	for(int i = 1; i <= n; ++i)res[i][i] = 1;
	while(b) {
		if(b & 1)times(res, a);
		times(a, a);
		b >>= 1;
	}
	for(int i = 1; i <= n; ++i)a[i] = res[i];
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].w);
	}
	sort(edge + 1, edge + m + 1);
	for(int i = 1; i <= n; ++i) {
		a[i][i] = 1;
	}
	int now = 0;
	if(edge[1].w > 0)return puts("Impossible"), 0;

	// puts("QWQ");
	for(int i = 1; i < m; ++i) {
		T[edge[i].from][edge[i].to] = 1;
		// printf("%d?\n", i);
		if(edge[i].w == edge[i + 1].w)continue;
		// printf("??");
		for(int j = 1; j <= n + 1 && now < edge[i + 1].w; ++j, ++now) {
			// printf("%d ", j);
			times(a, T);
			if(a[1][n] == 1)return printf("%d\n", now + 1), 0;
		}
		// puts("");
		for(int j = 1; j <= n; ++j) {
			b[j] = T[j];
		}
		ksm(b, edge[i + 1].w - now);
		times(a, b);
		now = edge[i + 1].w;
	}
	// puts("QWQW");
	T[edge[m].from][edge[m].to] = 1;
	for(int j = 1; j <= n + 1; ++j, now++) {
		times(a, T);
		if(a[1][n] == 1)return printf("%d\n", now + 1), 0;
	}
	return puts("Impossible"), 0;
}

是不是很模板啊