分道揚鑣

編號為1…N 的N個城市之間以單向路連接，每一條道路有兩個參數：路的長度和通過這條路需付的費用。

Bob和Alice生活在城市1，但是當Bob發現了Alice玩撲克時欺騙他之後，他決定與她翻臉，離開城市1前往城市N。Bob想儘快到達城市N，但是他的錢不多。

希望你幫助Bob找到一條從城市1到城市N的總費用不超過Bob的承受能力的最短路徑。

輸入的第一行是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

為每個測試用例輸出一行結果：總費用小於或等於最大費用K的最短路徑的長度。如果這樣的路徑不存在，則僅僅輸出 -1 。

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

測試數據的圖中可能有重邊、有自環。

這題有一定難度，但學完DFS和BFS就要能夠AC它。它是一道典型的搜索題，而且需要強剪枝（去掉 當前已知無效的搜索路徑），以便加快搜索速度。

 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 }