P3597 [POI2015]WYC

POI 合集。

非常显然的矩阵快速幂，由于边权只有 $3$ 所以拆点，存储 $f_{i,j},f_{i,j+1}$ 和 $f_{i,j+2}$ 表示以 $i$ 结尾的长度为 $j,j+1,j+2$ 的路径数量。最后再计一个 $sum$ 表示路径总数，得到转移矩阵 $B$。

预处理出 $B^1,B^2,\cdots,B^{61}$，然后倍增求解即可。时间复杂度 $\mathcal{O}(n^3\log k)$，有 $27$ 倍常数。注意矩阵每个数在任何时候都要对 $k$ 取 $\min$。

const int N = 120 + 5;
const ll inf = 2e18;

ll n, m, k, sz;
void add(ll &x, ll y) {x += y; if(x > inf) x = inf;}
ll mul(ll x, ll y) {return !y ? 0 : x > inf / y ? inf : x * y;}
struct Mat {
	ll a[N][N];
	Mat operator * (Mat x) {
		Mat y; mem(y.a, 0, sz + 1);
		for(int i = 1; i <= sz; i++)
			for(int j = 1; j <= sz; j++)
				for(int k = 1; k <= sz; k++)
					add(y.a[i][j], mul(a[i][k], x.a[k][j]));
		return y;
	}
	Mat operator / (Mat x) {
		Mat y; mem(y.a, 0, sz + 1);
		for(int i = 1; i <= sz; i++)
			for(int j = 1; j <= sz; j++)
				add(y.a[1][i], mul(a[1][j], x.a[j][i]));
		return y;
	}
} base, pw[N], I;

bool Med;
int main(){
	cin >> n >> m >> k, sz = n * 3 + 1;
	for(int i = 1; i <= n; i++) I.a[1][i] = 1;
	for(int i = 1; i <= m; i++) {
		int u, v, w; cin >> u >> v >> w;
		base.a[u][v + (w - 1) * n]++;
	} base.a[sz][sz] = 1;
	for(int i = 1; i < sz; i++) {
		if(i > n) base.a[i][i - n]++;
		for(int j = 1; j <= n; j++)
			base.a[i][sz] += base.a[i][j];
	} pw[0] = base;
	ll ans = 0, d = 0;
	while((I / pw[d]).a[1][sz] < k) {
		d++, pw[d] = pw[d - 1] * pw[d - 1];
		if(d > 61) puts("-1"), exit(0);
	}
	while(~(--d)) {
		Mat nw = I / pw[d];
		if(nw.a[1][sz] < k) ans += 1ll << d, I = nw;
	} cout << ans + 1 << endl;
	return 0;
}