转载请注明出处：http://www.cnblogs.com/zhishoumuguinian/p/8452518.html

思路：从第一城市开始dfs，提高效率需要进行剪枝，本题有两个限制，一个是道路限制，一个是钱的限制。假如我们到达 r 城市，而此时的总路径长度已经大于等于当前最短路径长度，这条路我们就没必要在继续进行下去了， 这是一个剪枝；如果我们花了同样的钱，走到同一城市，但是走的路比以前花同样的钱走的路短或等于，这条路就需要停止了。于是需要另外一个数组来记录花同样的钱，走到当前城市走的总路径长度。接下来粘上代码。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 int K, N, R;//存放钱数，城市数， 道路数 8 struct Road{
   //用邻接链表存储道路信息 9     int d, L, t;//终点， 道路长度， 过路费10 };11 vector< vector
         
           >G(110);12 int minL[110][10100];//minL[i][j]表示从1到i点的，花销为j的最短路的长度13 int minLen;//最短路线长度14 int totalLen;//当前经过路线长度15 int totalCost;//当前总的花销16 int visited[110];//标致数组17 void dfs(int s)18 {19     if( s==N)20     {21         minLen = min(minLen, totalLen);22         return;23     }24     for(int i=0; i < G[s].size(); ++i)25     {26         Road r = G[s][i];27         if( totalCost + r.t > K )//剪枝28         {29             continue;30         }31         32         if( !visited[r.d] )33         {34             if((r.L + totalLen >= minLen)||35                     (totalLen + r.L>=minL[r.d][r.t+totalCost]))//剪枝36             continue;37             totalLen  += r.L;38             totalCost += r.t;39             minL[r.d][r.t + totalCost] = totalLen;40             visited[r.d] = 1;41             dfs(r.d);42             totalLen  -= r.L;43             totalCost -= r.t;44             visited[r.d] = 0;45         }46     }47 }48 int main()49 {50     cin >> K >> N >> R;51     for(int i=0; i
          
           > s >> r.d >>r.L >>r.t;56 if(s != r.d)//起点等于终点的我们不读入57 {58 G[s].push_back(r);59 }60 }61 memset(visited, 0, sizeof(visited));62 minLen = 1 << 30;63 totalCost = 0;64 totalLen = 0;65 visited[1] = 1;66 for(int i=0; i < 110; i++ )67 for(int j=0; j < 10100; j++)68 minL[i][j] = (1 << 30);69 dfs(1);70 if( minLen < (1 << 30))71 {72 cout<< minLen << endl;73 }74 else75 cout<<-1 << endl;76 return 0;77 }