1724ROADS

转载请注明出处：http://www.cnblogs.com/zhishoumuguinian/p/8452518.html

思路：从第一城市开始dfs，提高效率需要进行剪枝，本题有两个限制，一个是道路限制，一个是钱的限制。假如我们到达 r 城市，而此时的总路径长度已经大于等于当前最短路径长度，这条路我们就没必要在继续进行下去了，这是一个剪枝；如果我们花了同样的钱，走到同一城市，但是走的路比以前花同样的钱走的路短或等于，这条路就需要停止了。于是需要另外一个数组来记录花同样的钱，走到当前城市走的总路径长度。接下来粘上代码。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 int K, N, R;//存放钱数，城市数， 道路数
 8 struct Road{//用邻接链表存储道路信息
 9     int d, L, t;//终点， 道路长度， 过路费
10 };
11 vector< vector<Road> >G(110);
12 int minL[110][10100];//minL[i][j]表示从1到i点的，花销为j的最短路的长度
13 int minLen;//最短路线长度
14 int totalLen;//当前经过路线长度
15 int totalCost;//当前总的花销
16 int visited[110];//标致数组
17 void dfs(int s)
18 {
19     if( s==N)
20     {
21         minLen = min(minLen, totalLen);
22         return;
23     }
24     for(int i=0; i < G[s].size(); ++i)
25     {
26         Road r = G[s][i];
27         if( totalCost + r.t > K )//剪枝
28         {
29             continue;
30         }
31         
32         if( !visited[r.d] )
33         {
34             if((r.L + totalLen >= minLen)||
35                     (totalLen + r.L>=minL[r.d][r.t+totalCost]))//剪枝
36             continue;
37             totalLen  += r.L;
38             totalCost += r.t;
39             minL[r.d][r.t + totalCost] = totalLen;
40             visited[r.d] = 1;
41             dfs(r.d);
42             totalLen  -= r.L;
43             totalCost -= r.t;
44             visited[r.d] = 0;
45         }
46     }
47 }
48 int main()
49 {
50     cin >> K >> N >> R;
51     for(int i=0; i<R; i++)
52     {
53         int s;
54         Road r;
55         cin>> s >> r.d >>r.L >>r.t;
56         if(s != r.d)//起点等于终点的我们不读入
57         {
58             G[s].push_back(r);
59         }
60     }
61     memset(visited, 0, sizeof(visited));
62     minLen = 1 << 30;
63     totalCost = 0;
64     totalLen = 0;
65     visited[1] = 1;
66     for(int i=0; i < 110; i++ )
67         for(int j=0; j < 10100; j++)
68                 minL[i][j] = (1 << 30);
69     dfs(1);
70     if( minLen < (1 << 30))
71     {
72         cout<< minLen << endl;
73     }
74     else
75     cout<<-1 << endl;
76     return 0;
77 }