题意:问从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 ", ans); } //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s. "; return 0; }