Codeforces 781D Axel and Marston in Bitland

题目链接：http://codeforces.com/contest/781/problem/D

${F[i][j][k][0,1]}$表示是否存在从${i-->j}$的路径走了${2^{k}}$步，${0,1}$表示第$1$步是走路还是骑车的。

倍增$Floyed$转移即可。

但是复杂度不对，考虑这个状态是记录的$bool$类型，将状态(${j}$)压一下位(可以用${bitset}$)。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<cstring>
 8 #include<map>
 9 #include<bitset>
10 using namespace std;
11 #define maxn 550
12 #define llg long long 
13 #define inf (llg)(1e18)
14 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
15 llg n,m;
16 bitset<maxn>f[61][2][maxn],rch,ch;
17 llg ans;
18 bool flag;
19 int main()
20 {
21     yyj("F");
22     cin>>n>>m;
23     for (llg i=1;i<=m;i++)
24     {
25         llg x,y,k;
26         scanf("%lld%lld%lld",&x,&y,&k);
27         f[0][k][x][y]=1;
28     }
29     for (llg i=1;i<=60;i++)
30         for (llg k=1;k<=n;k++)
31             for (llg j=1;j<=n;j++)
32                 for (llg z=0;z<=1;z++)
33                     if (f[i-1][z][j][k]) 
34                         f[i][z][j]|=f[i-1][z^1][k];
35     for(llg i=1;i<=n;i++)
36         if (f[60][0][1][i]) 
37         {
38             puts("-1");
39             return 0;
40         }
41     llg i;
42     for (rch[1]=1,i=59;i>=0;i--)
43       {
44           llg j;
45         for(ch=0,j=1;j<=n;j++)
46             if (rch[j]) ch|=f[i][flag][j];
47         if(ch.count()) rch=ch,ans+=(1LL<<i),flag^=1;
48     }
49     if(ans>inf) puts("-1");
50     else cout<<ans;
51     return 0;
52 }