链接:https://ac.nowcoder.com/acm/contest/331/D
题意:
小希现在要从寝室赶到机房,路途可以按距离分为N段,第i个和i+1个是直接相连的,只需要一秒钟就可以相互到达。
炫酷的是,从第i个到第i+2pi+2p个也是直接相连的(其中p为任意非负整数),只需要一秒钟就可以相互到达。
更炫酷的是,有K个传送法阵使得某些u,v之间也是直接相连的,只需要一秒钟就可以相互到达,当然,由于设备故障,可能会有一些u=v的情况发生。
现在小希为了赶路,她需要在最短的时间里从寝室(编号为1)到达机房(编号为N),她不希望到达这N个部分以外的地方(不能到达位置N+1),也不能走到比自己当前位置编号小的地方(比如从5走到3是非法的)。
她想知道最短的时间是多少。
思路:
bfs,先进对传送点,在进入i+2^p的最大点,或者,某个点存在传送门也进队。
感觉是个假算法。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXK = 20; struct Node
{
int _w;
int _step;
Node(int w,int step):_w(w), _step(step){}
};
pair<int, int> C[MAXK]; int Quick_M(int t)
{
int x = 2;
int res = 1;
while (t > 0)
{
if (t&1)
res *= x;
x *= x;
t >>= 1;
}
return res;
} int main()
{
int n,k;
cin >> n >> k;
for (int i = 1;i <= k;i++)
cin >> C[i].first >> C[i].second;
queue<Node> que;
que.emplace(1,0);
while (!que.empty())
{
//cout << 1 << endl;
Node now = que.front();
if (now._w == n)
break;
for (int i = 1;i <= k;i++)
{
if (C[i].first == now._w)
{
if (C[i].second <= now._w)
continue;
que.emplace(C[i].second, now._step + 1);
}
}
for (int i = 0;i <= 30;i++)
{
LL tx = now._w + Quick_M(i);
if (tx > n)
{
que.emplace(now._w + Quick_M(i - 1), now._step + 1);
break;
}
else
{
for (int i = 1;i <= k;i++)
{
if (C[i].first == tx)
{
if (C[i].second <= tx)
continue;
que.emplace(tx, now._step + 1);
}
}
}
}
que.pop();
}
cout << que.front()._step << endl; return 0;
}