dfs+剪枝

题意：
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
#include
#include
using namespace std;

int k,n,r;
struct road
{
    int d,l,t;
};
vector 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
        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
        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<