题意

$N$个城市，编号$1$到$N$。城市间有$R$条单向道路。 每条道路连接两个城市，有长度和过路费两个属性。 $Bob$只有$K$块钱，他想从城市$1$走到城市$N$。问最短共需要走多长的路。如果到不了$N$ ，输出$-1$

$2\leq N\leq100$

$0\leq K\leq 10000$

$1\leq R\leq 10000$

每条路的长度 $L$, $1 \leq L \leq 100$

每条路的过路费$T$, $0 \leq T\leq 100$

解题思路

从城市$1$开始深度优先遍历整个图，找到所有能到达$N$的走法，选一个最优的。

最优性剪枝

如果当前已经找到的最优路径长度为$L$，那么在继续搜索的过程中，总长度已经大于等于$L$的走法，就可以直接放弃，不用走到底了。 另一种通用的最优性剪枝思想——保存中间计算结果用于最优性剪枝： 如果到达某个状态$A$时，发现前面曾经也到达过$A$，且前面那次到达$A$所花代价更少，则剪枝。这要求保存到达状态$A$的到目前为止的最少代价。 用$midL[k][m]$表示：走到城市$k$时总过路费为$m$的条件下，最优路径的长度。若在后续的搜索中，再次走到$k$时，如果总路费恰好为$m$，且此时的路径长度已经超过$midL[k][m]$，则不必再走下去了。

标程

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

int K, N, R; // 钱，城市，道路

struct Road {
    int d, L, t; // 终点、长度、过路费
};

vector<vector<Road> > G(110); // 邻接表存储图
int minL[110][10010]; // minL[i][j]表示从1到i点，花费j的最短路径长度
int minLen; // 全局最短路径
int totalLen; // 当前路径长度
int totalCost; // 当前花费
int visited[110]; // 访问标记

void dfs(int s) {
    if (s == N) { // 到达终点
        if (totalLen < minLen) {
            minLen = totalLen;
        }
        return;
    }
    for (int i = 0; i < G[s].size(); ++i) {
        Road r = G[s][i];
        if (totalCost + r.t > K) continue; // 可行性剪枝
        if (visited[r.d]) continue; // 避免环路
        
        // 最优性剪枝
        if (totalLen + r.L >= minLen) continue;
        if (totalLen + r.L >= minL[r.d][totalCost + r.t]) continue;
        
        // 更新状态
        minL[r.d][totalCost + r.t] = totalLen + r.L;
        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() {
    scanf("%d%d%d", &K, &N, &R);
    for (int i = 0; i < R; ++i) {
        int s;
        Road r;
        scanf("%d%d%d%d", &s, &r.d, &r.L, &r.t);
        if (s != r.d) { // 避免自环
            G[s].push_back(r);
        }
    }
    
    // 初始化
    memset(visited, 0, sizeof(visited));
    memset(minL, 0x3f, sizeof(minL));
    totalLen = 0;
    minLen = 0x3f3f3f3f; // 用大数代替1<<30
    totalCost = 0;
    visited[1] = 1;
    
    dfs(1);
    
    if (minLen != 0x3f3f3f3f) {
        printf("%d\n", minLen);
    } else {
        printf("-1\n");
    }
    
    return 0;
}