跳转至

问题 F: 奇怪的电梯2

传送门：ZWGOJ | 洛谷 P1135

题目描述

原题面

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 \(i\) 层楼（\(1 \le i \le N\)）上有一个数字 \(K_i\)（\(0 \le K_i \le N\)）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： \(3, 3, 1, 2, 5\) 代表了 \(K_i\)（\(K_1=3\)，\(K_2=3\)，……），从 \(1\) 楼开始。在 \(1\) 楼，按“上”可以到 \(4\) 楼，按“下”是不起作用的，因为没有 \(-2\) 楼。那么，从 \(A\) 楼到 \(B\) 楼至少要按几次按钮呢？

对于 \(100 \%\) 的数据，\(1 \le N \le 200\)，\(1 \le A, B \le N\)，\(0 \le K_i \le N\)。

输入要求

共二行。

第一行为三个用空格隔开的正整数，表示 \(N, A, B\)（\(1 \le N \le 200\)，\(1 \le A, B \le N\)）。

第二行为 \(N\) 个用空格隔开的非负整数，表示 \(K_i\)。

输出要求

一行，即最少按键次数，若无法到达，则输出 \(-1\)。

样例

1
2
5 1 5
3 3 1 2 5

1
3

解法

解法和时间复杂度： (1)

  1. 此处时间复杂度为该解法的算法部分的时间复杂度，不是严谨的整题的时间复杂度
  • 法1：搜索 - 深搜 + 当前剪枝 + 答案剪枝 \(O(n)\)
  • 法2：搜索 - 广搜 + 队列 \(O(n)\)
  • 法3：最短路 - Floyd 算法 \(O(n^3)\)
  • 法4：最短路 - Bellman-Ford 算法 \(O(n^2)\)
  • 法5：最短路 - SPFA 算法 \(O(n)\)
  • 法6：最短路 - Dijkstra 算法 \(O(n\log n)\)
  • 法7：最短路 - Johnson 算法 \(O(n\log n)\)

法1：搜索 - 深搜 + 当前剪枝 + 答案剪枝

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const int MAXn = 200 + 9;
int d[MAXn];
int n, a, b;
lli step[MAXn];

void dfs(int x, int s) {
    if(s > step[b]) return;
    if(x < 1 || x > n) return;
    if(step[x] <= s) return;
    step[x] = s;
    dfs(x + d[x], s + 1);
    dfs(x - d[x], s + 1);
    return;
}

int main() {
    for(int i = 0; i <= MAXn - 3; i ++)
        step[i] = LLONG_MAX;
    scanf("%d%d%d", &n, &a, &b);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d[i]);
    dfs(a, 0);
    step[b] == LLONG_MAX ? printf("-1") : printf("%lld", step[b]);
    return 0;
}

法2：搜索 - 广搜 + 队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
typedef pair<int, lli> pil;
const int MAXn = 200 + 9;
int d[MAXn];
int n, a, b;
lli ans = LLONG_MAX;
queue<pil> que;
bool ved[MAXn];

int main() {
    scanf("%d%d%d", &n, &a, &b);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d[i]);
    que.push({a, 0});
    while(!que.empty()) {
        int p = que.front().first;
        lli s = que.front().second;
        que.pop();
        if(p == b) {ans = s; break; }
        if(p < 1 || p > n || ved[p]) continue;
        ved[p] = true;
        que.push({p + d[p], s + 1});
        que.push({p - d[p], s + 1});
    }
    ans == LLONG_MAX ? printf("-1") : printf("%lld", ans);
    return 0;
}

法3~7：最短路

此处最短路算法以 Dijkstra 算法为例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
#define int long long int
using namespace std;
typedef pair<int, int> pii;
const int MAXn = 200 + 9;
vector<int> g[MAXn];
int dis[MAXn];
priority_queue<pii> pq;    // first: dis; second: p

signed main() {
    for(int i = 0; i <= MAXn - 3; i ++) dis[i] = LLONG_MAX;
    int n, a, b;
    scanf("%lld%lld%lld", &n, &a, &b);
    for(int i = 1, ia; i <= n; i ++) {
        scanf("%lld", &ia);
        if(i + ia >= 1 && i + ia <= n) g[i].push_back(i + ia);
        if(i - ia >= 1 && i - ia <= n) g[i].push_back(i - ia);
    }
    dis[a] = 0;
    pq.push({0, a});
    while(!pq.empty()) {
        int now = pq.top().second, befdis = pq.top().first;
        pq.pop();
        for(int nxt : g[now]) {
            if(befdis + 1 < dis[nxt]) {
                dis[nxt] = befdis + 1;
                pq.push({befdis + 1, nxt});
            }
        }
    }
    dis[b] == LLONG_MAX ? printf("-1") : printf("%lld", dis[b]);
    return 0;
}