题意：
N个城市，编号1到N。城市间有R条单向道路。
每条道路连接两个城市，有长度和过路费两个属性。
Bob只有K块钱，他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N，输出-1
2<=N<=100
0<=K<=10000
1<=R<=10000
每条路的长度 L, 1 <= L <= 100
每条路的过路费T , 0 <= T <= 100
思路：
用d[i][j]表示从源点走到城市i并且花费为j的时候经过的最短距离。若在后续的搜索中，再次走到i时，如果总路费恰好为j，且此时的路径长度已经超过 d[i][j],则不必再走下去了。
1.深搜+剪枝
2.spfa+剪枝
实现：
1.
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <cstring> 6 using namespace std; 7 8 const int MAXN = 100; 9 const int MAXK = 10000; 10 const int INF = 0x3f3f3f3f; 11 12 struct node 13 { 14 int to, len, toll; 15 }; 16 vector<node> G[MAXN + 5]; 17 int k, n, m, s, t, l, T, minLen = INF; 18 19 bool vis[MAXN + 10]; 20 int d[MAXN + 5][MAXK + 5]; 21 22 void dfs(int now, int rem, int len) 23 { 24 if (now == n) 25 { 26 minLen = min(minLen, len); 27 return; 28 } 29 for (int i = G[now].size() - 1; i >= 0; i--) 30 { 31 if (!vis[G[now][i].to] && rem >= G[now][i].toll) 32 { 33 if (d[G[now][i].to][rem - G[now][i].toll] <= 34 len + G[now][i].len || len + G[now][i].len >= minLen) 35 continue; 36 d[G[now][i].to][rem - G[now][i].toll] = len + G[now][i].len; 37 dfs(G[now][i].to, rem - G[now][i].toll, len + G[now][i].len); 38 vis[G[now][i].to] = false; 39 } 40 } 41 } 42 43 int main() 44 { 45 cin >> k >> n >> m; 46 for (int i = 0; i < m; i++) 47 { 48 cin >> s >> t >> l >> T; 49 node tmp; 50 tmp.to = t; 51 tmp.len = l; 52 tmp.toll = T; 53 if (s != t) 54 G[s].push_back(tmp); 55 } 56 memset(d, 0x3f, sizeof(d)); 57 vis[1] = true; 58 dfs(1, k, 0); 59 if (minLen == INF) 60 puts("-1"); 61 else 62 cout << minLen << endl; 63 return 0; 64 }
2.
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <cstring> 6 #include <queue> 7 #include <functional> 8 using namespace std; 9 10 const int MAXN = 100; 11 const int MAXK = 10000; 12 const int INF = 0x3f3f3f3f; 13 14 struct node 15 { 16 int to, len, toll; 17 }; 18 vector<node> G[MAXN + 5]; 19 int k, n, m, s, t, l, T; 20 21 struct co 22 { 23 int now, cost; 24 }; 25 26 int d[MAXN + 5][MAXK + 5]; 27 int in[MAXN + 5][MAXK + 5]; 28 29 int spfa() 30 { 31 queue<co> q; 32 co start; 33 start.now = 1; 34 start.cost = 0; 35 q.push(start); 36 in[1][0] = true; 37 priority_queue<int, vector<int>, greater<int> > pq; 38 pq.push(INF); 39 while (!q.empty()) 40 { 41 co tmp = q.front(); 42 q.pop(); 43 int now = tmp.now; 44 int cost = tmp.cost; 45 if (now == n) 46 { 47 pq.push(d[n][cost]); 48 } 49 in[now][cost] = false; 50 for (int i = 0; i < G[now].size(); i++) 51 { 52 if (cost + G[now][i].toll <= k && 53 d[now][cost] + G[now][i].len < d[G[now][i].to][cost + G[now][i].toll]) 54 { 55 d[G[now][i].to][cost + G[now][i].toll] = d[now][cost] + G[now][i].len; 56 if (d[G[now][i].to][cost + G[now][i].toll] >= pq.top()) 57 continue; 58 if (!in[G[now][i].to][cost + G[now][i].toll]) 59 { 60 in[G[now][i].to][cost + G[now][i].toll] = true; 61 co son; 62 son.now = G[now][i].to; 63 son.cost = cost + G[tmp.now][i].toll; 64 q.push(son); 65 } 66 } 67 } 68 } 69 int minL = INF; 70 for (int i = 0; i <= k; i++) 71 { 72 minL = min(minL, d[n][i]); 73 } 74 return minL; 75 } 76 77 int main() 78 { 79 cin >> k >> n >> m; 80 for (int i = 0; i < m; i++) 81 { 82 cin >> s >> t >> l >> T; 83 node tmp; 84 tmp.to = t; 85 tmp.len = l; 86 tmp.toll = T; 87 if (s != t) 88 G[s].push_back(tmp); 89 } 90 memset(d, 0x3f, sizeof(d)); 91 for (int i = 0; i <= k; i++) 92 { 93 d[1][i] = 0; 94 } 95 int minLen = spfa(); 96 if (minLen >= INF) 97 puts("-1"); 98 else 99 cout << minLen << endl; 100 return 0; 101 }
最优性剪枝总结：
1. 从初始状态到当前状态的代价已经不小于目前找到的最优解，则剪枝。
2. 预测一下从当前状态到解的状态至少要花的代价W，如果W加上到达当前状态时已经花费的代价，必然不小于目前找到的最优解,则剪枝。
3. 如果到达某个状态A时，发现前面曾经也到达过A，且前面那次到达A所花代价更少，则剪枝。这要求记录到目前为止到达状态A时所能取得的最小代价。