https://www.luogu.org/problemnew/show/P1613
他有一个跑路机器，每次只能跑2（单位）路程，每相邻两个点的路程为1，也就是说如果连边1——》2——》3——》4——》5，路径长度为4，那么他可以一次从1跳到5；
n<=50;
我们要找的不是最短路径，而是一条路路程二进制数中1的个数最少；
这数据范围floyd已经够了，但是我们要提前处理一下连边；
我们将相距2 距离的两点距离设为1，这样再跑最短路就是正确答案；、
倍增思想体现在预处理上，；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=;
int g[maxn][maxn][maxn],n,m;
ll dis[maxn][maxn]; void maker_road()
{
for(int b=;b<=;b++)
{
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(g[i][k][b-]&&g[k][j][b-])
{
g[i][j][b]=;
dis[i][j]=;
}
}
}
}
}
} void floyd()
{
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
// if(dis[i][k]+dis[k][j]<dis[i][j])
//{
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
//}
}
}
}
}
int main()
{
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
g[x][y][]=;dis[x][y]=;
}
maker_road();
floyd();
printf("%lld\n",dis[][n]);
return ;
}
这里面的memset里面要开0x3f，开127会错出现负数，不知道为什么；
感谢 the_Death（https://www.luogu.org/space/show?uid=145411）的解答
{
因为在弗洛伊德算法里面有dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);，
并且你无法保证所有的dis[][]的所有都会被更新为1的个数，
这就表示有些dis[][]中会以memset给的初值进行加法运算。
而由于memset的特性，你在赋初值的时候赋0x3f也就是127，它的加法会爆long long。
}
这个博客里面有memeset的用法技巧