转载请注明出处：優YoU http://blog.csdn.net/lyy289065406/article/details/6692382
大致题意：
给定一个图，图中每条路都有 路长Length 和 过路费Toll 两个参数，一条路连接两个城市，任意两个城市之间有且仅有一条路。
现在只有 K 块钱，要求从起点City1出发，到达终点CityN的最短路，也就是说在 K 花费内的最短路。
解题思路：
这个题其实有很多种解法的，只不过是题目描述用的模型是最短路的模型，其实方法多种多样，Discuss里有同学用dijkstra+A*，也有人用BFS+优先队列，也有人用直接用STL的priotrity_queue+剪枝.....。
我用了DFS+剪枝去做：
每个城市只能到达1次，每次找满足 Toll<RestMoney 的城市；当NowLen>MinLen就回溯，无需往下搜索了；递归出口是遍历所有允许的情况。
其实这题难度不大，关键是建立 邻接链表 去存储相同Source的路径去提高搜索效率。
因为Bob每进入一个Cityk，他就只能选择以k为源点的路径走向下一个城市，此时应该直接枚举所有以k为源点的路径。若使用了其他存储方式，则必然每次都要在所有路径中重新寻找以k为源点的路径，再枚举，这相当浪费时间。
Source修正：
CEOI 1998
谷歌搜索“CEOI '98”第一个就是了。。。。
http://www.hsin.hr/ceoi98/
1 //Memory Time
2 //440K 250MS
3
4 /*--- C++ Class ---*/
5
6 #include<iostream>
7 using namespace std;
8
9 class Road
10 {
11 public:
12 int S,D,L,T; //Source,Destination,Length,Toll
13 int next; //指向相同Source的下一条边
14 };
15
16 class info
17 {
18 public:
19 info(int N,int R)
20 {
21 road=new Road[R+1];
22 vist=new bool[N+1];
23 ListTable_Head=new int[N+1];
24
25 memset(vist,false,sizeof(bool)*(N+1));
26 memset(ListTable_Head,-1,sizeof(int)*(N+1));
27 MinLen=1e7;
28 pr=0;
29 }
30 ~info()
31 {
32 delete[] road;
33 delete[] vist;
34 delete[] ListTable_Head;
35 }
36
37 void input(int R);
38 void output(void);
39 void DFS(int NowCity,int NowLen,int RestMoney,int N);
40
41 protected:
42 Road* road;
43 bool* vist;
44 int* ListTable_Head; //邻接链表头指针数组
45 int MinLen;
46 int pr; //road[]指针
47 };
48
49 void info::input(int R)
50 {
51 for(int i=1;i<=R;i++)
52 {
53 int s,d,l,t;
54 cin>>s>>d>>l>>t;
55
56 road[pr].S=s;
57 road[pr].D=d;
58 road[pr].L=l;
59 road[pr].T=t;
60 road[pr].next=ListTable_Head[s];
61 ListTable_Head[s]=pr++;
62 }
63 return;
64 }
65
66 void info::output()
67 {
68 cout<<(MinLen<1e7?MinLen:-1)<<endl;
69 return;
70 }
71
72 void info::DFS(int NowCity,int NowLen,int RestMoney,int N)
73 {
74 if(NowLen>MinLen)
75 return;
76
77 if(NowCity==N && RestMoney>=0 && NowLen<MinLen)
78 {
79 MinLen=NowLen;
80 return;
81 }
82
83 for(int i=ListTable_Head[NowCity];i!=-1;i=road[i].next)
84 {
85 int tD=road[i].D;
86 int tL=road[i].L;
87 int tT=road[i].T;
88
89 if(!vist[tD] && RestMoney>=tT)
90 {
91 vist[tD]=true;
92 DFS(tD,NowLen+tL,RestMoney-tT,N);
93 vist[tD]=false;
94 }
95 }
96 return;
97 }
98
99 int main(void)
100 {
101 int K,N,R; //Money,CityNum,RoadNum
102 while(cin>>K>>N>>R)
103 {
104 info poj1724(N,R);
105 poj1724.input(R);
106 poj1724.DFS(1,0,K,N);
107 poj1724.output();
108 }
109 return 0;
110 }
===============华丽的分割线================
1 //Memory Time
2 //444K 235MS
3
4 /*--- C++ Style ---*/
5
6 #include<iostream>
7 using namespace std;
8
9 const int inf=1e7;
10 const int CitySize=101;
11 const int RoadSize=10001;
12
13 struct
14 {
15 int S,D,L,T; //Source,Destination,Length,Toll
16 int next; //指向相同Source的下一条边
17 }road[RoadSize];
18
19 int pr; //road[]指针
20 int K,N,R; //Money,CityNum,RoadNum
21 int MinLen;
22 bool vist[CitySize];
23 int ListTable_Head[CitySize]; //邻接链表头指针数组
24
25 void DFS(int NowCity,int NowLen,int RestMoney)
26 {
27 if(NowLen>MinLen)
28 return;
29
30 if(NowCity==N && RestMoney>=0 && NowLen<MinLen)
31 {
32 MinLen=NowLen;
33 return;
34 }
35
36 for(int i=ListTable_Head[NowCity];i!=-1;i=road[i].next)
37 {
38 int tD=road[i].D;
39 int tL=road[i].L;
40 int tT=road[i].T;
41
42 if(!vist[tD] && RestMoney>=tT)
43 {
44 vist[tD]=true;
45 DFS(tD,NowLen+tL,RestMoney-tT);
46 vist[tD]=false;
47 }
48 }
49 return;
50 }
51
52 int main(void)
53 {
54 while(cin>>K>>N>>R)
55 {
56 memset(ListTable_Head,-1,sizeof(ListTable_Head));
57 memset(vist,false,sizeof(vist));
58 pr=0;
59 MinLen=inf;
60
61 for(int i=1;i<=R;i++)
62 {
63 int s,d,l,t;
64 cin>>s>>d>>l>>t;
65 road[pr].S=s;
66 road[pr].D=d;
67 road[pr].L=l;
68 road[pr].T=t;
69 road[pr].next=ListTable_Head[s];
70 ListTable_Head[s]=pr++;
71 }
72
73 DFS(1,0,K);
74
75 cout<<(MinLen<inf?MinLen:-1)<<endl;
76 }
77 return 0;
78 }
Sample Input
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
19
6
7
1 2 2 2
1 3 2 2
1 4 2 2
2 5 5 10
4 5 7 7
3 5 10 5
5 6 5 10
15
12
16
1 8 20 0
1 2 10 0
2 8 5 0
1 7 100 0
2 3 5 1
3 4 5 1
4 5 5 1
5 6 5 1
6 12 5 1
8 12 10 20
8 9 1 1
9 10 1 1
10 11 1 1
11 7 2 10
7 12 10 1
11 4 1 0
Sample Output
11
14
30