题目链接：http://codeforces.com/contest/781/problem/D
${F[i][j][k][0,1]}$表示是否存在从${i-->j}$的路径走了${2^{k}}$步，${0,1}$表示第$1$步是走路还是骑车的。
倍增$Floyed$转移即可。
但是复杂度不对，考虑这个状态是记录的$bool$类型，将状态(${j}$)压一下位(可以用${bitset}$)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<map>
#include<bitset>
using namespace std;
#define maxn 550
#define llg long long
#define inf (llg)(1e18)
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m;
bitset<maxn>f[][][maxn],rch,ch;
llg ans;
bool flag;
int main()
{
yyj("F");
cin>>n>>m;
for (llg i=;i<=m;i++)
{
llg x,y,k;
scanf("%lld%lld%lld",&x,&y,&k);
f[][k][x][y]=;
}
for (llg i=;i<=;i++)
for (llg k=;k<=n;k++)
for (llg j=;j<=n;j++)
for (llg z=;z<=;z++)
if (f[i-][z][j][k])
f[i][z][j]|=f[i-][z^][k];
for(llg i=;i<=n;i++)
if (f[][][][i])
{
puts("-1");
return ;
}
llg i;
for (rch[]=,i=;i>=;i--)
{
llg j;
for(ch=,j=;j<=n;j++)
if (rch[j]) ch|=f[i][flag][j];
if(ch.count()) rch=ch,ans+=(1LL<<i),flag^=;
}
if(ans>inf) puts("-1");
else cout<<ans;
return ;
}