寻路问题 - DFS+剪枝

视频上提到了两个重要的剪枝：

1. 保存到当前点u，花费cost的最短路径。如果使用再次访问函数并检查到已经累积的最短路径超过了存储的最优值，直接返回。
2. 保存已经搜索到的从起始点1到达目标点n的最短路径。如果当前累积的最短路径超过该值，则直接返回。

我试着加了第3个剪枝，即保存一个邻接矩阵,第i行第j列表示节点i到节点j所需要的最小花费，之后使用floyd-warshall多源点最短路径算法计算出两两之间的“最短路径”，这里即为两两之间的最小花费。可以想到，如果搜索的某个状态已经花费的钱数加上从该点到目标点的最小花费依然大于初始的金钱，则可以直接返回。尽管如此，这个剪枝在上述两个强力剪枝的前提下效果并不明显。如果数据强一些，应该会有所作为。

以下是仅包含两个剪枝的DFS实现：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 101;
const int MAX_COIN = 10001;
const int INF = 1e8;

struct Edge {
  int v, len, cost, next;
  Edge(int _v = 0, int _len = 0, int _cost = 0, int _next = 0) :
    v(_v), len(_len), cost(_cost), next(_next) {}
}edges[10010];

int head[MAXN], edgeNum = 0;
int shortestPath[MAXN][MAX_COIN];
bool visited[MAXN];
int K, N, R, S, D, L, T, minLen;

void dfs(int u, int usedMoney, int pathLen) {
  if (shortestPath[u][usedMoney] <= pathLen || pathLen >= minLen)
    return;
  shortestPath[u][usedMoney] = pathLen;
  if (u == N - 1) {
    minLen = min(minLen, pathLen);
    return;
  }

  visited[u] = true;
  int i;
  for (i = head[u]; ~i; i = edges[i].next) {
    int v = edges[i].v;
    if (!visited[v]) {
      dfs(v, usedMoney + edges[i].cost, pathLen + edges[i].len);
    }
  }
  visited[u] = false;
}

int main() {
  int i, j;
  scanf("%d%d%d", &K, &N, &R);
  memset(head, -1, sizeof(head));
  for (i = 0; i < R; i++) {
    scanf("%d%d%d%d", &S, &D, &L, &T);
    --S, --D;
    if (S != D) {
      edges[edgeNum] = Edge(D, L, T, head[S]);
      head[S] = edgeNum++;
    }
  }

  for (i = 0; i < N; i++)
    for (j = 0; j <= K; j++)
      shortestPath[i][j] = INF;
  minLen = INF;
  memset(visited, 0, sizeof(visited));
  dfs(0, 0, 0);
  printf("%d\n", minLen >= INF ? -1 : minLen);
  return 0;
}

寻路问题 - BFS+优先队列

对应深度优先搜索DFS，还有一种搜索叫做广度优先搜索BFS。这里也可以使用BFS来解决此题。

思想是从起始点开始加入队列，之后遍历所有相连的边，更新到该边的开销和长度，如果开销小于初始金钱数，就入队列。而队列本身可以看做存放路径的最小堆，对顶元素永远是目前所有访问过的点中从起始点开始路径最短的一个。终止条件为，队列首元素为目标点。这是因为队列中只保存开销小于初始金钱数的状态，而第一个访问到目标点的状态一定是路径最短的一个。

实现代码如下：

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 101;

struct Edge {
  int v, len, cost, next;

  Edge (int _v = 0, int _len = 0, int _cost = 0, int _next = 0) :
    v(_v), len(_len), cost(_cost), next(_next) {}

  bool operator < (const Edge& other) const {
    return this->len > other.len;
  }
}edges[10010];
int head[MAXN], edgeNum = 0;
int K, N, R, S, D, L, T;

int bfs() {
  priority_queue<Edge> q;
  q.push(Edge());
  while (!q.empty()) {
    Edge top = q.top();
    q.pop();
    int u = top.v;
    if (u == N - 1) {
      return top.cost > K ? -1 : top.len;
    }
    for (int i = head[u]; ~i; i = edges[i].next) {
      if (top.cost + edges[i].cost <= K)
        q.push(Edge(edges[i].v, top.len + edges[i].len, top.cost + edges[i].cost));
    }
  }
  return -1;
}

int main() {
  int i, j;
  scanf("%d%d%d", &K, &N, &R);
  memset(head, -1, sizeof(head));
  for (i = 0; i < R; i++) {
    scanf("%d%d%d%d", &S, &D, &L, &T);
    --S, --D;
    if (S != D) {
      edges[edgeNum] = Edge(D, L, T, head[S]);
      head[S] = edgeNum++;
    }
  }
  printf("%d\n", bfs());
  return 0;
}