洛谷OJ：P1135 奇怪的电梯

这题有三种解法，1.搜索 2.最短路 3.DP

1.直接写个DFS就行了

#include <iostream>
#include <cstdio>
using namespace std;

const int maxn = 200+10, inf = 0x3f3f3f3f;
int k[maxn], ans = inf;
bool vis[maxn];
int n, a, b;

void dfs(int cur, int s) {
    if(cur == b) {
        ans = ans < s ? ans : s;
        return;
    }
    if(s > ans || (vis[cur] != 0 && s > vis[cur]) ) return;
    vis[cur] = 1;
    if(cur-k[cur] >= 0)
        if(!vis[cur-k[cur]])
            dfs(cur-k[cur], s+1);
    if(cur+k[cur] <= n)
        if(!vis[cur+k[cur]])
            dfs(cur+k[cur], s+1);
    vis[cur] = 0;
}

int main() {
    scanf("%d %d %d", &n, &a, &b);
    for(int i = 1; i <= n; i++) scanf("%d", &k[i]);
    dfs(a,0);
    if(ans-inf) printf("%d\n", ans);
    else printf("-1\n");
    return 0;
}

2.上个SPFA模板

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
int V, E_quan, n, s, e;
struct Edge {
    int v;
    int cost;
    Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost) {}
};
vector<Edge> E[MAXN];
void addEdge(int u, int v, int w) {
    E[u].push_back(Edge(v, w));
}
bool vis[MAXN];     //  在队列标志
int cnt[MAXN];      //  每个点的入列队次数
int dist[MAXN];
bool SPFA(int start, int n) {
    memset(vis, false, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));

    vis[start] = true;
    dist[start] = 0;
    queue<int> que;

    while (!que.empty()) {
        que.pop();
    }
    que.push(start);
    memset(cnt, 0, sizeof(cnt));
    cnt[start] = 1;

    while (!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;

        for (int i = 0; i < E[u].size(); i++) {
            int v = E[u][i].v;
            if (dist[v] > dist[u] + E[u][i].cost) {
                dist[v] = dist[u] + E[u][i].cost;
                if (!vis[v]) {
                    vis[v] = true;
                    que.push(v);
                    if (++cnt[v] > n) {
                        return false;   //  cnt[i]为入队列次数，用来判定是否存在负环回路
                    }
                }
            }
        }
    }
    return true;
}

int main(){
    int temp;
    cin >> n >> s >> e;
    for ( int i = 1; i <= n ;i++ ) {
        cin >> temp;
        if ( i - temp > 0 ) {
            addEdge(i,i-temp,1);
            E_quan++;
        }
        addEdge(i,i+temp,1); E_quan++;
    }
    if(SPFA(s,e)) {
        if ( dist[e] == INF ) printf("-1");
        else printf("%d",dist[e]);
    }
    else cout << "此图有负环回路" << endl;
    return 0;
}

3.DP

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 200+10, inf = 0x3f3f3f3f;
int k[maxn], dp[maxn];
int n, a, b;

int main() {
    scanf("%d %d %d", &n, &a, &b);
    for(int i = 1; i <= n; i++) scanf("%d", &k[i]);
    bool isloop = true;
    memset(dp, 0x3f, sizeof(dp));
    dp[a] = 0;
    while(isloop) {
        isloop = false;
        for(int i = 1; i <= n; i++) {
            int temp = dp[i];
            if(i - k[i] >= 1) {
                if(dp[i-k[i]] > dp[i]+1) {
                    dp[i-k[i]] = dp[i]+1;
                    isloop = true;
                }
            }
            if(i + k[i] <= n) {
                if(dp[i+k[i]] > dp[i]+1) {
                    dp[i+k[i]] = dp[i]+1;
                    isloop = true;
                }
            }
        }
    }
    if(dp[b] != inf) printf("%d", dp[b]);
    else printf("-1");
    return 0;
}