题目大意：
编号为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 ≤ 100
Output为每个测试用例输出一行结果：总费用小于或等于最大费用K的最短路径的长度。如果这样的路径不存在，则仅仅输出 -1 。
Sample Input5 6 71 2 2 32 4 3 33 4 2 41 3 4 14 6 2 13 5 2 05 4 3 2
Sample Output11
Hint测试数据的图中可能有重边、有自环。
原本天真地以为邻接表+DFS+简单剪枝就能过 结果还是TLE 之前看题解发现了一个 特殊的剪枝 用上就AC了 minlen[node][fee]数组记录1~ node 点在 fee 花费时的最短距离 假如搜索到 i 点而花费为 fe 时 le 超过了已记录到的 minlen[i][fe] 则可结束本次搜索 #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; int s[10005],d[10005],l[10005],t[10005],flag[105]; int k,n,r,len,minlen[105][10005],first[105],nexti[10005]; void DFS(int i,int le,int fe) { if(fe>k || le>minlen[i][fe] || le>len) return; /// 用minlen数组记下 i 点在 fe 花费时的最短距离,若超过则可停止继续搜索了 if(i==n) { len=min(len,le); //printf("%d\n",len); return ; } else { if(le<minlen[i][fe]) /// 若存在更短的距离 则更新minlen的值 for(int j=fe;j<=k;j++) minlen[i][j]=le; int in=first[i]; while(in!=-1) { if(!flag[d[in]]) { flag[d[in]]=1; /// 避免自环情况 DFS(d[in],le+l[in],fe+t[in]); flag[d[in]]=0; } in=nexti[in]; } /// 邻接表遍历 } } int main() { while(~scanf("%d%d%d",&k,&n,&r)) { memset(flag,0,sizeof(flag)); for(int i=1;i<101;i++) for(int j=0;j<10001;j++) minlen[i][j]=200000; memset(first,-1,sizeof(first)); for(int i=1;i<=r;i++) { scanf("%d%d%d%d",&s[i],&d[i],&l[i],&t[i]); nexti[i]=first[s[i]]; first[s[i]]=i; } /// 建邻接表 可避免重边引起的错误 flag[1]=1; len=INF; DFS(1,0,0); if(len==INF) printf("-1\n"); else printf("%d\n",len); } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/8605948.html
