DFS(剪枝) POJ 1724 ROADS

题目传送门

题意：问从1到n的最短路径，同时满足花费总值小于等于k

分析：深搜+剪枝，如果之前走过该点或者此时的路劲长度大于最小值就不进行搜索。

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/11 星期三 10:14:14

* File Name     :POJ_1724.cpp

 ************************************************/

//#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <cmath>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e2 + 10;

const int E = 1e4 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

int k, n, m;

struct Edge {

    int v, w, len, nex;

    Edge () {}

    Edge (int v, int w, int len, int nex) : v (v), w (w), len (len), nex (nex) {}

}edge[E];

int head[N], d[N];

bool vis[N];

int e;

void init(void) {

    memset (head, -1, sizeof (head));

    e = 0;

}

void add_edge(int u, int v, int w, int len) {

    edge[e] = Edge (v, w, len, head[u]);

    head[u] = e++;

}

int ans;

void DFS(int u, int L, int cost)    {

    if (u == n) {

        if (L < ans)    ans = L;

        return ;

    }

    for (int i=head[u]; ~i; i=edge[i].nex)  {

        Edge &r = edge[i];

        if (cost - r.w < 0 || L + r.len > ans)  continue;

        if (vis[r.v])   continue;

        vis[r.v] = true;

        DFS (r.v, L + r.len, cost - r.w);

        vis[r.v] = false;

    }

}

int main(void)    {

    while (scanf ("%d%d%d", &k, &n, &m) == 3)   {

        init ();

        for (int u, v, w, len, i=1; i<=m; ++i)    {

            scanf ("%d%d%d%d", &u, &v, &len, &w);

            add_edge(u, v, w, len);

        }

        ans = INF;

        memset (vis, false, sizeof (vis));

        vis[1] = true;

        DFS (1, 0, k);

        if (ans == INF) ans = -1;

        printf ("%d\n", ans);

    }

   //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}