1.木棒
2. roads
题意：
N 个以数字 1 … N 命名的城市与单向道路相连。每条道路都有两个与之相关的参数：道路长度和道路需要支付的通行费。鲍勃和爱丽丝曾经住在城市 1。在注意到爱丽丝在他们喜欢玩的纸牌游戏中作弊后，鲍勃与她分手并决定搬走 到城市 N。他想尽快到达那里可能，但他缺钱。我们想帮助 Bob 找到他可以用他有的钱买得起的从城市 1 到城市 N 的最短路径。
输入的第一行包含整数 K，0 <= K <= 10000，Bob 在路上可以花费的最大硬币数。
第二行包含整数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 注意不同的道路可能有相同的来源城市和目的地城市。
输出的第一行也是唯一一行应该包含从城市 1 到城市 N 的最短路径的总长度，其总通行费小于或等于 K 个硬币。如果这样的路径不存在，则只应将数字 -1 写入输出。
输入：
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
输出：
11
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int k,n,r;
struct road
{
int d,l,t;
};
vector<road> v[110];
int minlen=1<<30;
int totallen,totalcost;
int st[110];
int minl[110][10010];//表示走到i点是，花费为j的最短路径
void dfs(int s)
{
if(s==n)
{
minlen=min(minlen,totallen);
return;
}
for(int i=0;i<v[s].size();i++)
{
int d=v[s][i].d;
if(!st[d])
{
if(totalcost+v[s][i].t>k) continue;//可行性剪枝
if(totallen+v[s][i].l>=minlen) continue;//基本最优性剪枝
if(totallen+v[s][i].l>=minl[d][totalcost+v[s][i].t]) continue;//处处最优剪枝
totalcost+=v[s][i].t;
totallen+=v[s][i].l;
minl[d][totalcost]=totallen;
st[d]=1;
dfs(d);
st[d]=0;
totalcost-=v[s][i].t;
totallen-=v[s][i].l;
}
}
}
int main()
{
cin>>k>>n>>r;
int s;
road R;
for(int i=0;i<r;i++)
{
cin>>s>>R.d>>R.l>>R.t;
if(s!=R.d) v[s].push_back(R);
}
memset(minl,0x3f,sizeof minl);
st[1]=1;
dfs(1);
if(minlen<(1<<30)) cout<<minlen<<endl;
else cout<<"-1"<<endl;
return 0;
}
