题目链接: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 }