$dp[0/1][i][x][y]$表示起始边为0/1, 走$2^i$ 步, 是否能从$x$走到$y$
则有转移方程
$dp[z][i][x][y]\mid=dp[z][i-1][x][k]\&dp[z\wedge1][i-1][k][y]$
复杂度 $O(k_0n^3)$, 其中$k_0=log(1e18)$
这里可以用bitset优化第四维的递推, bitset底层相当于若干个64bit数, 可以优化64的常数
复杂度$O(\frac{k_0n^3}{\omega})$
#include <iostream>
#include <bitset>
#include <cstdio>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll; int n, m;
bitset<> f[][][], pre, now; int main() {
scanf("%d%d", &n, &m);
REP(i,,m) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
f[w][][u][v] = ;
}
REP(i,,) REP(z,,) REP(x,,n) REP(y,,n) {
if (f[z][i-][x][y]) f[z][i][x]|=f[z^][i-][y];
}
ll ans = , z = ;
pre[] = ;
PER(i,,) {
now.reset();
REP(j,,n) if (pre[j]) now|=f[z][i][j];
if (now.count()) z^=, ans^=1ll<<i, pre=now;
}
printf("%lld\n",ans>1e18?-:ans);
}