Time Limit: 300ms Description 编号为1…N 的N个城市之间以单向路连接，每一条道路有两个参数：路的长度和通过这条路需付的费用。
Bob和Alice生活在城市1，但是当Bob发现了Alice玩扑克时欺骗他之后，他决定与她翻脸，离开城市1前往城市N。Bob想尽快到达城市N，但是他的钱不多。
希望你帮助Bob找到一条从城市1到城市N的总费用不超过Bob的承受能力的最短路径。
Input 输入的第一行是3个整数 K, N, R ，其中：
K：表示Bob能承受的最大费用，0 ≤ K ≤ 10000 N：表示城市的总数，2 ≤ N ≤ 100 R：表示道路的条数，1 ≤ R ≤ 10000接下来的R行，每行用S D L T（以空格隔开）表示一条道路：
S：表示道路的出发城市，1 ≤ S ≤ N D：表示道路的目标城市，1 ≤ D ≤ N L：表示道路的长度，1 ≤ L ≤ 100 T：表示通过这条道路需付的费用，0 ≤ T ≤ 100Output 为每个测试用例输出一行结果：总费用小于或等于最大费用K的最短路径的长度。如果这样的路径不存在，则仅仅输出 -1 。
Sample Input 5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2
Sample Output 11
Hint 测试数据的图中可能有重边、有自环。
显然，可以通过判断当前路径的花费是否已超过K来剪枝，但是这道题只是这样的话还是会得到TLE
解决方法是，可以开一个 minlen[ i ][ fe ] 的二维数组来记录， 表示 到点 i 时花费为 fe 的路径长度为 minlen[ i ][ fe ]， 此时 就可以通过判断 当前位于i点且路径花费为fe路径长度为len时 len是否超过minlen[ i ][ fe ] 来剪枝。
#include<cstdio> #include<iostream> #include<vector> #include<cstring> const int inf=0x3f3f3f3f; using namespace std; struct node { int len,fare,aim; }; vector<node>G[105]; int minlen[105][10005]; bool book[105]; int K,N,R,S,D,L,T,Road; void dfs(int i,int step,int money) { if(money>K||step>Road||step>minlen[i][money]) return; if(i==N){ Road=min(Road,step); return; } else{ if(step<minlen[i][money]) for(int e=money;e<=K;e++) minlen[i][e]=step; for(int j=0;j<G[i].size();j++){ if(!book[G[i][j].aim]){ money+=G[i][j].fare; ///if(money>K)continue;之前因为多了这两句所以一直WA，想想为什么，为什么剪枝放在这里就错（这里不能去continue！） step+=G[i][j].len; ///if(step>Road)continue;之前因为多了这两句所以一直WA，想想为什么，为什么剪枝放在这里就错（这里不能去continue！） book[G[i][j].aim]=1; dfs(G[i][j].aim,step,money); money-=G[i][j].fare; step-=G[i][j].len; book[G[i][j].aim]=0; } } } return; } int main() { while(~scanf("%d%d%d",&K,&N,&R)) { struct node qq; /*初始化*/ memset(book,0,sizeof(book)); memset(minlen,inf,sizeof(minlen)); for(int i=1;i<=N;i++)G[i].clear(); /*建邻接表*/ for(int i=1;i<=R;i++){ scanf("%d%d%d%d",&S,&D,&L,&T); if(S==D)continue;///这一句有没有都对，它会选择最优的路径，所以自环其实是没有影响 qq.aim=D,qq.fare=T,qq.len=L,G[S].push_back(qq);///用结构体vector建邻接表，可避免重边引起的错误，存储起点对应的终点和路径长度、费用三个信息 } Road=inf;///初始化为无穷大 book[1]=1; dfs(1,0,0); if(Road==inf) ///路径不存在 printf("-1\n"); else printf("%d\n",Road); } return 0; }剪枝算法按照其判断思路可大致分成两类:可行性剪枝及最优性剪枝。 1 . 可行性剪枝 ：该方法判断继续搜索能否得出答案，如果不能直接回溯。 2 . 最优性剪枝： 最优性剪枝，又称为上下界剪枝，是一种重要的搜索剪枝策略。它记录当前得到的最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯。
