倍增
直接用图论算法必然解决不了这个问题，所以可以使用倍增算法优化。
我们遇到这个题该怎么想，首先，题目要求的值是1到n的最小代价。代价是路径的二进制中1的个数。
我们先预处理出每两点之间是否有边权和为(1 << k)的路径。这样的话，代价预处理就可以只需考虑1的情况，因为每个数都可以由(1<<k1)+(1<<k2)所累加而来，所以像2，3这种数都可以用1凑出来。
处理之后，一开始连接的边代价都为1，然后可以找到许多可以横跨许多点的代价为1的路径，这样的话， 就用floyd转移代价即可。
#include <bits/stdc++.h>
#define N 1000111
#define int long long
using namespace std;
int n, m, mp[101][101];
int cek[101][101][100]; //cek[i][j][k]表示是否i到j之间有边权和为(1 << k)的路径
signed main()
{
scanf("%lld%lld", &n, &m);
memset(mp, 10, sizeof(mp));
for (int i = 1; i <= m; i++)
{
int a, b;
scanf("%lld%lld", &a, &b);
cek[a][b][0] = 1;
mp[a][b] = 1;
}
for (int t = 1; t <= 64; t++)
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (cek[i][k][t - 1] && cek[k][j][t - 1])
{
cek[i][j][t] = 1;
mp[i][j] = 1;
}
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
printf("%lld", mp[1][n]);
return 0;
}
/*
7 8
1 6
5 1
6 4
4 5
5 2
3 7
7 5
2 3
rignt ans: 2
*/