Description：

给一张有向图，每条边的边权只可能是 $1,2,3$ 中的一种，求出第 $k$ 小的路径的长度，

$1\leqslant n\leqslant 40,1\leqslant m\leqslant 1000,1\leqslant k\leqslant 10^{18}$

Solution：

矩阵乘法应该是很容易想到的，具体操作的话就是把一个点拆成三个点，分别代表向外连出去的不同边权，然后每个点的第一个点向 $0$ 连一条边， $0$ 连一个自环，这样就可以做到找出很多不同长度的路径，即从某个点开始到 $0$ 结束算一个路径，这样我们只要不停倍增出有 $k$ 条路径时就是答案，注意只有一个点不算路径。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

int n,m;

ll l;

#define MAXN 41

int id(int k,int x){return (k - 1) * 3 + x;}

struct matrix

{

	ll m[MAXN * 3][MAXN * 3];

	matrix(){memset(m,0,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 0;i <= 3 * n;++i)

		{

			for(int j = 0;j <= 3 * n;++j)

			{

				for(int k = 0;k <= 3 * n;++k)

				{

					c.m[i][j] += a.m[i][k] * b.m[k][j];

					if(c.m[i][j] >= l)

					{

						for(int x = 1;x <= 3 * n;++x)

							for(int y = 1;y <= 3 * n;++y)

								c.m[x][y] = -1;

						return c;

					}

				}

			}

		}

		return c;

	}

}f[1000];

bool check(matrix m)

{

	ll sum = 0;

	for(int i = 1;i <= n;++i)

	{

		sum += m.m[id(i,1)][0] - 1;

		if(sum >= l)return false;

	}

	return true;

}

int main()

{

	scanf("%d%d%lld",&n,&m,&l);

	for(int i = 1;i <= n;++i)

	{

		++f[0].m[id(i,1)][id(i,2)];

		++f[0].m[id(i,2)][id(i,3)];

		++f[0].m[id(i,1)][0];

	}

	++f[0].m[0][0];

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		++f[0].m[id(a,c)][id(b,1)];

	}

	int cur = 0;

	for(;;++cur)

	{

		if(cur > 64)

		{

			puts("-1");

			return 0;

		}

		f[cur + 1] = f[cur] * f[cur];

		if(f[cur + 1].m[1][1] == -1)break;

		if(!check(f[cur + 1]))break;

	}

	matrix res = f[cur];

	ll ans = (1ll << cur);

	for(int i = cur - 1;i >= 0;--i)

	{

		if(check(res * f[i]))

		{

			res = res * f[i];

			ans += (1ll << i);

		}

	}

	cout << ans << endl;

	return 0;

}