洛谷P1135多题解

 解法1：BFS，有n个节点每个节点最多被访问一次，所以BFS时间复杂度为O(n)。注意a==b的特判。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 205;
int n, a, b;
int k[N], s[N];
bool st[N];
int dy[2];
int main() {cin >> n >> a >> b;if (a == b) {cout << 0 << endl;return 0;}for (int i = 1; i <= n; i++) {cin >> k[i];}memset(s, -1, sizeof(s));s[a] = 0;st[a] = true;queue<int> q;q.push(a);while (q.size()) {int t = q.front();q.pop();dy[0] = k[t], dy[1] = -k[t];for (int i = 0; i < 2; i++) {int u = t + dy[i];if (u == b) {cout << s[t] + 1 << endl;return 0;}if (u < 1 || u > n || st[u])continue;st[u] = true;s[u] = s[t] + 1;q.push(u);}}cout << -1 << endl;return 0;
}

解法2：DFS，时间复杂度是O(2^n)有点大。剪了枝还是TLE

#include<iostream>
#include<climits>
#include<cstring>
using namespace std;
int n, a, b;
int k[205];
bool st[205];
int minn = INT_MAX;
void dfs(int u, int step){if(step >= minn)return;if(u == b){minn = min(minn, step);return;}if(u < 1 || u > n || st[u])return;st[u] = true;int up = u + k[u];if(up <= n){dfs(up, step + 1);}int down = u - k[u];if(down >= 1){dfs(down, step + 1);}st[u] = false;
}
int main(){cin >> n >> a >> b;for(int i = 1; i <= n; i++){cin >> k[i];}dfs(a, 0);if(minn == INT_MAX)cout << -1 << endl;else cout << minn << endl;return 0;
}

解法3：迪杰斯特拉堆优化，时间复杂度为O((v+e)logv)

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 205;
int k[N];
bool st[N];
int dist[N];
typedef pair<int, int>PII;
int n, a, b;
int dijkstra(){memset(dist, 0x3f, sizeof(dist));dist[a] = 0;priority_queue<PII, vector<PII>, greater<PII>>heap;heap.push({0, a});while(heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if(ver == b)return distance;if(st[ver])continue;st[ver] = true;int up = ver + k[ver];if(up <= n && dist[up] > distance + 1){dist[up] = distance + 1;heap.push({dist[up], up});}int down = ver - k[ver];if(down >= 1 && dist[down] > distance + 1){dist[down] = distance + 1;heap.push({dist[down], down});}}return -1;
}
int main(){cin >> n >> a >> b;for(int i = 1; i <= n; i++){cin >> k[i];}int t = dijkstra();cout << t << endl;return 0;
}

解法4：SPFA，时间复杂度最坏是O(n^2)

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 205;
int n, a, b;
int dist[N];
bool st[N];
int k[N];
int spfa(){memset(dist, 0x3f, sizeof(dist));dist[a] = 0;queue<int> q;q.push(a);st[a] = true;while(q.size()){int t = q.front();q.pop();st[t] = false;int up = t + k[t];if(up <= n && dist[up] > dist[t] + 1){dist[up] = dist[t] + 1;if(!st[up]){q.push(up);st[up] = true;}}int down = t - k[t];if(down >= 1 && dist[down] > dist[t] + 1){dist[down] = dist[t] + 1;if(!st[down]){q.push(down);st[down] = true;}}}if(dist[b] == 0x3f3f3f3f)return -1;return dist[b];
}
int main(){cin >> n >> a >> b;for(int i = 1; i <= n; i++){cin >> k[i]; }int t = spfa();cout << t << endl;return 0;
}