深度优先搜索（DFS）

主要有邻接表和邻接矩阵两种。

主要的剪枝方法有：

1.标记已经走过的点，避免重复路过。但需要将其撤回标记，以保证新的路线能够经过该点。

2.加以判断，如果当前状态已经不是最优解可以不再继续搜索。

3.动态存储和比较最优解。

OpenJudge - 1724:ROADS

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int K, N, R;
struct Road {int d, L, t;
};
int minLen;
int totalLen, totalcost;
int visited[55];
int minL[101][10010];
vector<vector<Road>> G(110);
void dfs(int s)
{if (s == N){minLen = min(minLen, totalLen);return;}for (int i = 0; i < G[s].size(); i++){Road r = G[s][i];if (r.t + totalcost > K)//第一处剪枝，如果此前已经不满足题意，就跳过该步骤return;if (r.L + totalLen >= minLen)//第二次剪枝，同上continue;if (r.L + totalLen >= minL[r.d][totalcost + r.t])//第三次剪枝，动态存储，如果到达此位置时，已经可以提前判断不是最优解，则放弃该步骤。continue;minL[r.d][totalcost + r.t] = r.L + totalLen;//第三次剪枝，存储每一步的状态，以比较是否是最优解。if (!visited[r.d]){totalLen += r.L;//totalcost += r.t;//第四处剪枝，标记已经走过的点，不再重复走。visited[r.d] = 1;//dfs(r.d);visited[r.d] = 0;//需要解除标记，以保证新的路线能够走这些点。totalLen -= r.L;totalcost -= r.t;}}
}
int main()
{cin >> K >> N >> R;for (int i = 0; i < R; i++){int s;Road r;cin >> s >> r.d >> r.L >> r.t;G[s].push_back(r);}totalcost = 0;totalLen = 0;visited[1] = 1;minLen = 1 << 30;for (int i = 0; i < 101; i++)for (int j = 0; j < 10010; j++)minL[i][j] = (1 << 30);dfs(1);if (minLen < (1 << 30))cout << minLen << endl;elsecout << -1 << endl;return 0;
}

奇怪的电梯 - 洛谷

#include<iostream>
#include<cmath>
using namespace std;
int N, A, B;
int k[255];
int visited[255];
int minans = 1 << 30;
void dfs(int i, int ans)
{if (ans > minans)//第一次剪枝，如果当前状态已经不是最优解，可提前放弃搜索。return;if (i == B) {minans = min(minans, ans);return;}if (i + k[i] >= 1 && i + k[i] <= N && i + k[i] != i && !visited[i]) {visited[i] = 1;//第二次剪枝，标记已走过的点避免重复走，但需要将其撤掉，以保证新的路线能够重新走到该点。dfs(i + k[i], ans + 1);visited[i] = 0;}if (i - k[i] >= 1 && i - k[i] <= N && i - k[i] != i && !visited[i]) {visited[i] = 1;dfs(i - k[i], ans + 1);visited[i] = 0;}
}
int main()
{cin >> N >> A >> B;for (int i = 1; i <= N; i++)cin >> k[i];dfs(A, 0);if (minans < (1 << 30))cout << minans;else cout << -1;return 0;
}