洛谷-P1135 奇怪的电梯（BFS或单源最短路）

题目描述

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

输入格式

共二行。

第一行为33个用空格隔开的正整数，表示N,A,B(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N)。

第二行为N*N*个用空格隔开的非负整数，表示K_i*K**i*。

输出格式

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

输入输出样例

输入 #1

5 1 5
3 3 1 2 5

输出 #1

3

---

解法一：BFS搜索，从一个位置开始搜索上下所能到达的点，如果未被访问且在范围内，则入队。

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> seq(205);
vector<bool> used(205, false);
int start, tail;

struct Node
{
    int pos, step;
    Node(int pEle, int sEle) : pos(pEle), step(sEle) {}
};

int solve()
{
    queue<Node> q;
    q.push(Node(start, 0));
    used[start] = true;

    while (!q.empty()) {
        Node tmp = q.front(); q.pop();
        if (tmp.pos == tail) return tmp.step;

        int up = tmp.pos + seq[tmp.pos];
        if (up <= n && !used[up]) {
            used[up] = true;
            q.push(Node(up, tmp.step + 1));
        }

        int down = tmp.pos - seq[tmp.pos];
        if (0 <= down && !used[down]) {
            used[down] = true;
            q.push(Node(down, tmp.step + 1));
        }
    }

    return -1;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> start >> tail;
    for (int i = 1; i <= n; ++i) cin >> seq[i];

    cout << solve() << endl;

    return 0;
}

解法二：单源最短路。从一个点出发到达另一个点，固定起点和终点，典型的单源最短路。方法有Bellman-Ford、SPFA、Dijkstra，其中Dijkstra算法时间复杂度最优（图中无负环）