传送门：POJ1724 ROADS
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=110;
const int INF=0x3f3f3f;
int vis[maxn];struct Node{int d,L,T;
}tmp;
vector<vector<Node> >mp(maxn); /*题目说，不同的边可能有相同的起点和终点，所以用二维数组mp[][]
来存不合适，因为这样的边没法存，pass掉（之前我就用数组存的，wa了好久）*/
int k,n,r;
int minL[maxn][10010]; //minL[i][j]表示从1到i花销为j的最短路的长度。
ll minway,way; //当前最短路径长度，当前路径长度void dfs(int x,int cost){//printf("x=%d\n",x);vis[x]=1;//可行性剪枝if(cost>k) return ;//最优性剪枝if(way>minway||way>minL[x][cost]) return ;minL[x][cost]=way;//到达边界if(x==n){//printf("way=%d\n",way);minway=min(minway,way);return ;}int len=mp[x].size();for(int i=0;i<len;i++){//cout<<"x="<<x<<",i="<<i<<endl;int tp=mp[x][i].d;if(!vis[tp]){//cout<<"mp["<<x<<"]["<<i<<"].L="<<mp[x][i].L<<endl;way+=mp[x][i].L;dfs(tp,cost+mp[x][i].T);//不走这点vis[tp]=0;way-=mp[x][i].L;}}
}int main(){scanf("%d%d%d",&k,&n,&r);memset(vis,0,sizeof(vis));memset(minL,0x3f,sizeof(minL));int s;for(int i=0;i<r;i++){scanf("%d%d%d%d",&s,&tmp.d,&tmp.L,&tmp.T);if(s!=tmp.d)mp[s].push_back(tmp);}minway=INF;way=0;dfs(1,0);if(minway==INF){printf("-1\n");}else{printf("%lld\n",minway);}return 0;
}