CF780FAxelandMarstoninBitland

Solution

首先，能够比较明显的看出来，它的路径类型都是形如 \(2^i\) ，所以我们能够想到倍增。

然后我们观察数据范围，发现 \(n\leq 500\) 。我去，那我乱搞不就行了

考虑倍增的DP，设状态 \(dp[0/1][s][u][v]\) 为从 \(u\) 到 \(v\) 存在一条以 \(0/1\) 开头，长度为 \(2^s\) 的路径，那么状态转移方程为 \(dp[0/1][s][u][v]=dp[0/1][s-1][u][k]\or dp[1/0][s-1][k][v]\) ，其中 \(k\) 为中间转移点。

然后考虑如何计算答案，因为二进制的某个性质，当前位有 \(1\) 要比后面都是 \(1\) 还大，所以从高位向低位贪心，并用一个 \(tmp\) 来表示状态，及时更新。

细节：因为大于 \(10^{18}\) 就输出 \(-1\) ，所以开 \(long~long\) ，并在统计答案的时候及时判断。

代码

#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N=510;
const ll INF=1e18;
int n,m,now;
ll ans,pow2[100];
bitset f[2][70][N],g,tmp;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
int main(){
n=read();m=read();
for(int i=1,u,v,w;i<=m;i++){
u=read();v=read();w=read();
f[w][0][u][v]=1;
}
for(int i=1;i<=60;i++)
for(int u=1;u<=n;u++)
for(int v=1;v<=n;v++){
if(f[0][i-1][u][v]!=0) f[0][i][u]|=f[1][i-1][v];
if(f[1][i-1][u][v]!=0) f[1][i][u]|=f[0][i-1][v];
}
if(f[0][60][1].count()){
puts("-1");
return 0;
}
now=0;tmp[1]=1;pow2[0]=1;
for(int i=1;i<=60;i++) pow2[i]=pow2[i-1]*2;
for(int i=60;i>=0;i--){
g.reset();
for(int j=1;j<=n;j++)
if(tmp[j]) g|=f[now][i][j];
if(g.count()!=0){
now^=1;tmp=g;
ans+=pow2[i];
}
}
if(ans>INF) puts("-1");
else printf("%lld\n",ans);
return 0;
}