[POI2015] WYC

显然矩阵乘法
发现点数和边权非常小，所以可以考虑拆点

把每个点拆为 \(u_1\),\(u_2\),\(u_3\)， 初始：\(u_1\to u_2\),\(u_2\to u_3\)，每一条加边：\(u+(w-1)\times n\to v\)

因为 \(k\) 非常大，所以考虑倍增优化

注意：答案会爆 long long，需要使用 unsigned long long

// Problem: P3597 [POI2015] WYC
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3597
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define int ull // 会爆 long long 
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 125; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n, m, k; 
struct matrix
{
	int a[N][N]; 
	matrix () { mem (a, 0); } 
	matrix operator * (const matrix &b) const
	{
		matrix ans; 
		for (int i = 0; i < N; i ++ )
		{
			for (int k = 0; k < N; k ++ )
			{
				for (int j = 0; j < N; j ++ )
					ans.a[i][j] += a[i][k] * b.a[k][j]; 
            }
        }
        return ans; 
    }
} a, f[N]; 
bool check (matrix a)
{
    int sum = 0;
    for (int i = 1; i <= n; i ++ )
    {
    	sum += a.a[i][0] - 1; // 每次会多加一个贡献（画图模拟）
    	if (sum >= k) return 1; 
    }
    return 0; 
}
signed main ()
{
	n = rd (int), m = rd (int), k = rd (int); 
    f[0].a[0][0] = 1;
    for(int i = 1; i <= n; i ++ )
    	a.a[i][i] = 
    	f[0].a[i][0] = f[0].a[i][i + n] = f[0].a[i + n][i + 2 * n] = 1;
    for (int i = 1; i <= m; i ++ )
    {
    	int u = rd (int), v = rd (int), w = rd (int); 
        f[0].a[u + (w - 1) * n][v] ++ ; 
    }
    int i; 
    for (i = 1; ; i ++ )
    {
        if (i > 65) { printf ("-1\n"); return 0; } 
        f[i] = f[i - 1] * f[i - 1]; 
        if (check (f[i])) break; 
    }
    i -- ; 
    int ans = 0; 
    for (; i >= 1; i -- )
    {
    	matrix tmp = a * f[i]; 
        if (!check (tmp)) a = tmp, ans += (1llu << i);
    }
    matrix tmp = a * f[0]; 
    if (!check (tmp)) a = tmp, ans += (1llu << 0);
    printf ("%lld\n", (ll)ans); 
    return 0; 
}