题意：

给定K单位资金，N个城市，R条路径（每条路径包含from,to,dis,cost四个信息），要求找出在费用可承担的情况下从城市1到城市N的最短路径。

思路：

由输入信息构图，然后从城市1出发执行DFS直到到达城市N结束，同时进行以下优化：

可行性剪枝：若走到该点时的总费用已超过K则continue;

最优性剪枝：若走到该点时的路径长度已大于总的最短路径则continue；

记忆性搜索：用mindis[d][nowcost]记录当前结点的最短路径，其中d表示当前结点，nowcost表示到达此结点时的花销，若到达d结点,花销nowcost时的路径长度大于mindis[d][nowcost]则continue；

除以上剪枝之外还需注意每次扩展结点进行DFS后要重置路径、花费、标记信息，同时由于可能存在不同路径起始点与终点相同但路径不同的情况，不能使用普通数组描述的邻接矩阵，可用自定义结构体的二维数组表示。

代码实现：

//OpenJudge1724 ROADS
#include <iostream>
#include <cstring>
#include <climits>
#include <vector>
using namespace std;struct road{int to;int dis;int cost;road(){}road(int tt,int dd,int cc):to(tt),dis(dd),cost(cc){}
};vector<vector<road> > city(110);
int mindis[110][10010];
bool vis[110];
int n,k,r,s,d,l,t;
int minpath=INT_MAX;
int cost=0;
int path=0;
bool flag=false;void dfs(int source)
{if(source==n){minpath=min(minpath,path);flag=true;return;}for(int i=0;i<city[source].size();i++){int d=city[source][i].to;if(!vis[d]){			int nowcost=cost+city[source][i].cost;int nowpath=path+city[source][i].dis;if(nowcost>k||nowpath>=mindis[d][nowcost]||nowpath>=minpath)continue;path+=city[source][i].dis;cost+=city[source][i].cost;mindis[d][cost]=path;vis[d]=1;dfs(d);vis[d]=0;path-=city[source][i].dis;cost-=city[source][i].cost;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>k>>n>>r;for(int i=0;i<r;i++){cin>>s>>d>>l>>t;city[s].push_back(road(d,l,t));}for(int i=1;i<=n;i++)for(int j=0;j<=10000;j++)mindis[i][j]=INT_MAX;memset(vis,0,sizeof(vis));vis[1]=1;dfs(1);if(flag)cout<<minpath<<endl;elsecout<<-1<<endl;return 0;
}