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;
}

  

上一篇:mysql查看表使用的数据库引擎


下一篇:Eclipse Missing artifact jdk.tools:jdk.tools:jar:1.6