編號為1…N 的N個城市之間以單向路連接，每一條道路有兩個參數：路的長度和通過這條路需付的費用。
Bob和Alice生活在城市1，但是當Bob發現了Alice玩撲克時欺騙他之後，他決定與她翻臉，離開城市1前往城市N。Bob想盡快到達城市N，但是他的錢不多。
希望你幫助Bob找到一條從城市1到城市N的總費用不超過Bob的承受能力的最短路徑。
Input輸入的第一行是3個整數 K, N, R ，其中：
K：表示Bob能承受的最大費用，0 ≤ K ≤ 10000
N：表示城市的總數，2 ≤ N ≤ 100
R：表示道路的條數，1 ≤ R ≤ 10000
接下來的R行，每行用S D L T（以空格隔開）表示一條道路：
S：表示道路的出發城市，1 ≤ S ≤ N
D：表示道路的目標城市，1 ≤ D ≤ N
L：表示道路的長度，1 ≤ L ≤ 100
T：表示通過這條道路需付的費用，0 ≤ T ≤ 100
Output為每個測試用例輸出一行結果：總費用小於或等於最大費用K的最短路徑的長度。如果這樣的路徑不存在，則僅僅輸出 -1 。
Sample Input5 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
Hint測試數據的圖中可能有重邊、有自環。
這題有一定難度，但學完DFS和BFS就要能夠AC它。它是一道典型的搜索題，而且需要強剪枝（去掉 當前已知無效的搜索路徑），以便加快搜索速度。
一看題目，發現很像PTA裡的一道題目：<a href = "https://pta.patest.cn/pta/test/558/exam/4/question/9931">旅游規劃</a>，但是解決思路不同，旅游規劃那道題是用迪傑斯特拉算法的變形，這道題的思路是搜索所有城市1到城市N的可能路徑，然後選一條費用不超過K的最短路徑，有則輸出最短路徑長度，沒有則輸出-1。 偽代碼：
1 DFS（LGraph G， int i， int K）
2 {
3 if（i == N）//說明搜索到了N城市
4 bestDist = currDist; //最短路徑=當前路徑
5 else
6 {
7 循環每一個G中下標為i的頂點的鄰接點
8 if(visited[adjvertex] == false && ck+adjvertex.cost<= K
9 && currDist+adjvertex.dist<bestDist)
10 { /*如果鄰接點沒有被訪問，剪枝：當前費用ck+到鄰接點費用小於等於K，當前距離+到鄰接點的距離小於最短距離*/
11 ck+=adjvertex.cost;
12 currDist+=adjvertex.dist;
13 DFS(G, adjvertex, K);
14 ck-=adjvertex.cost;
15 currDist-=adjvertex.dist;
16
17 }
18 }
19
20 return bestDist;
21 }
1 //DFS 函數自己實現才有收獲
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <stdbool.h>
5 #include <string.h>
6
7 #define MaxVertexNum 101 /* 最大頂點數設為101 */
8 typedef int Vertex; /* 用頂點下標表示頂點,為整型 */
9 typedef struct{ /* 邊的權值設為距離和花費 */
10 int dist, cost;
11 }WeightType;
12
13 /* 邊的定義 */
14 typedef struct ENode *PtrToENode;
15 struct ENode{
16 Vertex V1, V2; /* 有向邊<V1, V2> */
17 WeightType Weight; /* 權重 */
18 };
19 typedef PtrToENode Edge;
20
21 /* 鄰接點的定義 */
22 typedef struct AdjVNode *PtrToAdjVNode;
23 struct AdjVNode{
24 Vertex AdjV; /* 鄰接點下標 */
25 WeightType Weight; /* 邊權重 */
26 PtrToAdjVNode Next; /* 指向下一個鄰接點的指針 */
27 };
28
29 /* 頂點表頭結點的定義 */
30 typedef struct Vnode{
31 PtrToAdjVNode FirstEdge;/* 邊表頭指針 */
32 } AdjList[MaxVertexNum]; /* AdjList是鄰接表類型 */
33
34 /* 圖結點的定義 */
35 typedef struct GNode *PtrToGNode;
36 struct GNode{
37 int Nv; /* 頂點數 */
38 int Ne; /* 邊數 */
39 AdjList G; /* 鄰接表 */
40 };
41 typedef PtrToGNode LGraph; /* 以鄰接表方式存儲的圖類型 */
42
43 LGraph BuildGraph();
44 LGraph CreateGraph( int VertexNum );
45 void InsertEdge( LGraph Graph, Edge E );
46 int DFS(LGraph G, int n);
47
48 bool visited[MaxVertexNum];
49 int K;
50 int ck; //當前花費
51 int bestDist; //最好的路程
52 int currDist; //當前的路程
53
54 int main()
55 {
56 int result;
57 scanf("%d",&K);
58 LGraph G = BuildGraph();
59 memset(visited, false, sizeof(visited));
60 ck = currDist = 0;
61 visited[1] = true;
62 bestDist = 0xffff;
63 result = DFS(G, 1);
64 if (bestDist == 0xffff) //說明沒有符合的路徑，返回-1
65 result = -1;
66 printf("%d\n",result);
67 getchar();getchar();
68 return 0;
69 }
70
71 LGraph CreateGraph( int VertexNum )
72 { /* 初始化一個有VertexNum個頂點但沒有邊的圖 */
73 Vertex V;
74 LGraph Graph;
75
76 Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立圖 */
77 Graph->Nv = VertexNum;
78 Graph->Ne = 0;
79 /* 初始化鄰接表頭指針 */
80 /* 注意：這裡默認頂點編號從1開始，到(Graph->Nv) */
81 for (V=1; V<=Graph->Nv; V++)
82 Graph->G[V].FirstEdge = NULL;
83
84 return Graph;
85 }
86
87 void InsertEdge( LGraph Graph, Edge E )
88 {
89 PtrToAdjVNode NewNode;
90
91 /* 插入邊 <V1, V2> */
92 /* 為V2建立新的鄰接點 */
93 NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
94 NewNode->AdjV = E->V2;
95 NewNode->Weight = E->Weight;
96 /* 將V2插入V1的表頭 */
97 NewNode->Next = Graph->G[E->V1].FirstEdge;
98 Graph->G[E->V1].FirstEdge = NewNode;
99 }
100
101 LGraph BuildGraph()
102 {
103 LGraph Graph;
104 Edge E;
105 Vertex V;
106 int Nv, i;
107
108 scanf("%d", &Nv); /* 讀入頂點個數 */
109 Graph = CreateGraph(Nv); /* 初始化有Nv個頂點但沒有邊的圖 */
110
111 scanf("%d", &(Graph->Ne)); /* 讀入邊數 */
112 if ( Graph->Ne != 0 ) { /* 如果有邊 */
113 E = (Edge)malloc( sizeof(struct ENode) ); /* 建立邊結點 */
114 /* 讀入邊，格式為"起點 終點 權重"，插入鄰接表 */
115 for (i=0; i<Graph->Ne; i++) {
116 scanf("%d %d %d %d", &E->V1, &E->V2, &E->Weight.dist, &E->Weight.cost);
117 InsertEdge( Graph, E );
118 }
119 }
120 return Graph;
121 }
