poj1724 ROADS

Posted on | In |

题意

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

解题思路

从城市 1开始深度优先遍历整个图，找到所有能到达 N 的走法，
选一个最优的。
优化：

1) 如果当前已经找到的最优路径长度为L ,那么在继续搜索的过程中，总长度已经大
于L的走法，就可以直接放弃，不用走到底了

2) 用midL[k][m] 表示：走到城市k时总过路费为m的条件下，最优路径的长度。若在
后续的搜索中，再次走到k时，如果总路费恰好为m，且此时的路径长度已经超过
midL[k][m],则不必再走下去了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define MAX 100
int k,N,r,totalLen,totalCost; 
using namespace std;
int vis[MAX]; 
//minL[i][j]表示走到i城市 总过路费为J的条件下 最优路径的长度 
int minL[110][10100];
int minLen=1<<30;//
struct road{
	int d,l,t;
	road(int dd,int ll,int tt):d(dd),l(ll),t(tt){
		
	} 
}; 
vector<vector<road> > v(110);//!!

//起点从N开始 
void dfs(int n){
	//递归出口 走到第n个城市 
	if(n==N){
		minLen = min(minLen,totalLen);//!!!可能不只一条 
		return;
	}
	for(int i=0;i<v[n].size();i++){//起点为N的road数量 
		int d=v[n][i].d;//所到达的城市
		if(!vis[d]){

				if(totalCost+v[n][i].t>k) continue;
					//终点为n 花费同样多时 最短的路径数量 
					if(totalLen+v[n][i].l>minLen||totalLen+v[n][i].l>minL[d][totalCost+v[n][i].t])//!!
						continue; 
				
				
			totalCost+=v[n][i].t;
			totalLen+=v[n][i].l;
			minL[d][totalCost]=totalLen;
			
				vis[d]=1;
				dfs(d);
				vis[d]=0;
			totalCost-=v[n][i].t;
			totalLen-=v[n][i].l;
			
		}
	
		
		
	}
	
}
int main(){
	//钱 城市数 路数 
	cin>>k>>N>>r;
	for(int i=0;i<r;i++)
	{
		int s,e,l,r;
		cin>>s>>e>>l>>r;
		if(s!=e)
		v[s].push_back(road(e,l,r));//!!终点 长度 费用 
		
	}
	for( int i = 0;i < 110; ++i )
	for( int j = 0; j < 10100; ++ j )
	minL[i][j] = 1 << 30;
	memset(vis,0,sizeof(vis));
	totalLen = 0;
	totalCost = 0;
	vis[1] = 1;
	minLen = 1 << 30;
	dfs(1);
	if( minLen < (1 << 30))
	cout << minLen << endl;
	else
	cout << "-1" << endl;
	return 0;
}