传送门：炫酷路途
题目描述
小希现在要从寝室赶到机房，路途可以按距离分为N段，第i个和i+1个是直接相连的，只需要一秒钟就可以相互到达。
炫酷的是，从第i个到第
个也是直接相连的（其中p为任意非负整数），只需要一秒钟就可以相互到达。
更炫酷的是，有K个传送法阵使得某些u,v之间也是直接相连的，只需要一秒钟就可以相互到达，当然，由于设备故障，可能会有一些u=v的情况发生。
现在小希为了赶路，她需要在最短的时间里从寝室(编号为1)到达机房(编号为N)，她不希望到达这N个部分以外的地方（不能到达位置N+1），也不能走到比自己当前位置编号小的地方（比如从5走到3是非法的）。
她想知道最短的时间是多少。
输入描述:
第一行输入两个整数N,K，表示路途的段数和传送法阵的数量。
从第二行开始K行，每行两个整数
,
表示两个位置之间相连。
输出描述:
输出一个整数，表示从寝室到机房最短的时间是多少秒。
示例2
输出
1
这个题让我明白了二进制还可以这么用……之前二进制接触的太少了。
1e9的范围，也就2的30多次方，如果不用传送阵，也就是说走30多步即可到达。
那具体的怎么求呢？
把两个点的距离转换成二进制，二进制中有几个1就需要走几步，因为可以一下走2的次方的距离，所以二进制有几个1就说明要走多少步。可以用树状数组lowbit（x）来求，就是x & -x，求的是x中最低位的1，例如：6（110），lowbit（6）=2=2^1
如果用传送阵，K<=15,最多的情况也就是2^15种情况，可以枚举出来，从0到2^15依次是不用传送阵，用第一个，用第二个，用第一个和第二个……
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e9 + 10;
int n, k;
int lowbit(int x) { return x & -x; }
struct node
{
int u;
int v;
}p[20];
int step(int x)
{
int ans = 0;
while (x) {
x -= lowbit(x);
ans++;
}
return ans;
}
bool cmp(node x, node y)
{
return x.u < y.u;
}
int main()
{
while (cin>>n>>k)
{
for (int i = 0; i < k; i++)
cin >> p[i].u >> p[i].v;
sort(p, p + k, cmp);
int ans = step(n - 1);
for (int i = 0; i < 1 << k; i++)
{ //这里就是那最多2^15次的情况，
int t = 1, sum = 0;
for (int j = 0; j < k; j++)
{ //这里是枚举每个传送阵
if (i&j << k)
{
if (t > p[j].u)
continue;
sum += step(p[j].u - t) + 1;
t = p[j].v;
}
}
if (t > n)
continue;
sum += step(n - t);
ans = min(ans, sum);
}
cout << ans << endl;
}
}