鏈接：https://ac.nowcoder.com/acm/contest/331/D

題意：

小?，F(xiàn)在要從寢室趕到機(jī)房，路途可以按距離分為N段，第i個和i+1個是直接相連的，只需要一秒鐘就可以相互到達(dá)。

炫酷的是，從第i個到第

思路:

bfs，先進(jìn)對傳送點，在進(jìn)入i+2^p的最大點，或者，某個點存在傳送門也進(jìn)隊。

感覺是個假算法。

代碼：

#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; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/YDDDD/p/10353798.html

總結(jié)

以上是生活随笔為你收集整理的牛客寒假5-D.炫酷路途的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。