POJ1724:ROADS

---

描述:

N cities named with numbers 1 … N are connected with one-way roads. Each road has two parameters associated with it : the road length and the toll that needs to be paid for the road (expressed in the number of coins). Bob and Alice used to live in the city 1. After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N. He wants to get there as quickly as possible, but he is short on cash.

We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.

输入： The first line of the input contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way. The second line contains the integer N, 2 <= N <= 100, the total number of cities.

The third line contains the integer R, 1 <= R <= 10000, the total number of roads.

Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters :

S is the source city, 1 <= S <= N D is the destination city, 1 <= D <= N L is the road length, 1 <= L <= 100 T is the toll (expressed in the number of coins), 0 <= T <=100

Notice that different roads may have the same source and destination cities.

输出： The first and the only line of the output should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins. If such path does not exist, only number -1 should be written to the output.

样例输入：

5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2

样例输出：

11

题目大概意思：

有N个城市，编号从1到N。城市间有R条单向的通路。每条通路是连接两个城市，每条路有长度和过路费这样两个属性。现在我们有K块钱，让我们找从1能够到达N的最短路径的长度，如果找不到输出-1。

范围： 2 <= N <= 100 (城市数) 0 <= K <= 10000 (拥有的钱) 1 <= R <= 10000 (道路数) 1 <= L <= 100 (每条路的长度) 0 <= T <= 100 (每条路的路费)

大概思路:

首先我们知道这是一个寻找最短路径的问题，用深搜做的话，是试图找到所有能够到达终点的路，然后 得到最短的一条路径。

然后具体到这道题还有路费这个问题，这是判断是否能够到达终点的一个条件。

然后我们可以用一个邻接表来存储各个路的属性，以及路与路之间的连接关系。用二维vector可方便实现。

然后因为用深搜找最短路径其实是复杂度是大约指数级别的，那么就很大可能会用到剪枝，剪枝又包括最优性剪枝和可行性剪枝。可行性剪枝就是说要走某一步时，我们判断根据条件能否走那一步，比如这道题的钱的限制，我们就需要判断我们的钱是否够走那个点。然后是最优性剪枝，就是说我们达到某个点时，发现之前达到过此处并且更优。具体到这道题就是，当我们将要走一个点a，但是发现走a点的路径的长度已经是比我们之前得出的最短路径的长度要长了，那么我们就没有必要走下去了。其次，还有一个最优性剪枝就是当我们发现之前也达到过a点并且花费的钱都是一样的，但是这次去a点的路径长度更长，花相同的钱但是长度却更长，那也没有必要进行下去了。

AC代码

#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; struct Rode { int d,l,t; //表示终点、长度、路费，不需要起点因为起点是vector的行号 }; int K,N,R; //表示钱，城市数，道路数 vector<vector<struct Rode > > map(110); int visit[110]; int minLen = 1 << 30; //最短路径的长度 int len,cost; //当前路径长度，花费 int temp[110][10010]; //当花费多少钱走到哪个点的时候的路径长度 void dfs(int i) { //边界条件 if(i == N) { if(minLen > len) minLen = len; //选择是否更新最短长度 return ; } //循环所有直接连接的点 int size = map[i].size(); for(int j = 0; j < size; j ++) { Rode rode = map[i][j]; //走过了 if(visit[rode.d] != 0) continue; //可行性剪枝 if(cost + rode.t > K) continue; //最优性剪枝 if(len + rode.l > minLen) continue; if(len + rode.l > temp[rode.d][cost+ rode.t]) continue; //尝试走rode.d temp[rode.d][cost + rode.t] = len + rode.l; len += rode.l; cost += rode.t; visit[rode.d] == 1; dfs(rode.d); //回到这里时，应该还原 这一步不走rode.d len -=rode.l; cost -=rode.t; visit[rode.d] == 0; } } int main() { scanf("%d %d %d",&K,&N,&R); for(int i = 0 ; i < R; i ++ ) { Rode rode; int s; scanf("%d %d %d %d",&s,&rode.d,&rode.l,&rode.t); if(s!=rode.d) { map[s].push_back(rode); //s为地点，就在vector的s行号 } } memset(visit,0,sizeof(visit)); for(int i = 0; i< 110; i++) for(int j = 0; j < 10010; j ++) temp[i][j] = 1 << 30; visit[1] = 1; //城市1已经走过 len = 0;cost = 0; dfs(1); if(minLen == 1 << 30) printf("-1\n"); else printf("%d\n",minLen); return 0; }