题目大意：
编号为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 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
测试数据的图中可能有重边、有自环。
原本天真地以为邻接表+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[],d[],l[],t[],flag[];
int k,n,r,len,minlen[][],first[],nexti[]; 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!=-)
{
if(!flag[d[in]])
{
flag[d[in]]=; /// 避免自环情况
DFS(d[in],le+l[in],fe+t[in]);
flag[d[in]]=;
}
in=nexti[in];
} /// 邻接表遍历 } }
int main()
{
while(~scanf("%d%d%d",&k,&n,&r))
{
memset(flag,,sizeof(flag));
for(int i=;i<;i++)
for(int j=;j<;j++)
minlen[i][j]=;
memset(first,-,sizeof(first)); for(int i=;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[]=; len=INF;
DFS(,,); if(len==INF) printf("-1\n");
else printf("%d\n",len);
} return ;
}