poj 1724 ROADS 很水的dfs

题意：给你N个城市和M条路和K块钱，每条路有话费，问你从1走到N的在K块钱内所能走的最短距离是多少

直接dfs搜一遍就是

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stdlib.h>
 6 #include <vector>
 7 #include <queue>
 8 #include <stack>
 9 #define loop(s,i,n) for(i = s;i < n;i++)
10 #define cl(a,b) memset(a,b,sizeof(a))
11 const int maxn = 521;
12 const int inf = 99999999;
13 using namespace std;
14 struct node
15 {
16     int u,v,len,cost;
17     int next;
18 }edges[10001];
19 int g[105];
20 int vis[105];
21 int ans;
22 int n,m;
23 void dfs(int u,int val,int dis)
24 {
25     vis[u] = 1;
26     if(val < 0)
27     return;
28     if(u == n)
29     {
30         if(ans > dis)
31         ans = dis;
32         return ;
33     }
34 
35     if(ans < dis)
36     return;
37 
38     int i;
39 
40     for(i = g[u];i != -1;i = edges[i].next)
41     {
42         int v;
43         v = edges[i].v;
44         int len,cost;
45         len = edges[i].len;
46         cost = edges[i].cost;
47         if(!vis[v])
48         {
49             dfs(v,val-cost,dis+len);
50             vis[v]--;
51         }
52     }
53 
54 }
55 
56 int main()
57 {
58     int u,v,l,t;
59     int k;
60     while(~scanf("%d %d %d",&k,&n,&m))
61     {
62         int i;
63         memset(vis,0,sizeof(vis));
64         cl(g,-1);
65         int cnt = 0;
66         while(m--)
67         {
68             scanf("%d%d%d%d",&u,&v,&l,&t);
69             edges[cnt].u = u;
70             edges[cnt].v = v;
71             edges[cnt].len = l;
72             edges[cnt].cost = t;
73             edges[cnt].next = g[u];
74             g[u] = cnt;
75             cnt++;
76         }
77         ans = inf;
78         dfs(1,k,0);
79         if(ans != inf)
80         printf("%d
",ans);
81         else
82         puts("-1");
83     }
84     return 0;
85 }

View Code