小单刷题笔记之寻路问题（剪枝思想）

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int K,N,R;
struct Road{
	int d,l,t;
};
vector<vector<Road>>G(110);
int minL[110][10010];
int minLen;
int totalLen;
int totalCost;
int vis[110];
void dfs(int s){
	if(s==N){
		minLen=min(totalLen,minLen);
		return ;
	}
	for(int i=0;i<G[s].size();i++){
		Road r=G[s][i];
		if (totalCost+r.t>K)continue;
		if(!vis[r.d]){
			if(totalLen+r.l>=minLen)continue;
			if(totallen+r.l>=minL[r.d][totalCost+r.t]){
				continue;
			}
			minL[r.d][totalCost+r.t]=totaLen+r.l;
			totalLen+=r.l;
			totalCost+=r.t;
			vis[r.d]=1;
			dfs(r.d);
			vis[r.d]=0;
			totalLen-=r.l;
			totalCost-=r.t;
		}
	}
}


int main(){
	cin>>K>>N>>R;
	for(int i=0;i<R;++i){
		int s;
		Road r;
		cin>>s>>r.d>>r.l>>r.t;
		if(s!=r.d){
			G[s].push_back(r);
		}
	}
	for(int i=0;i<110;i++){
		for(int j=0;j<10010;j++){
			minL[i][j]=1<<30;
		}
	}
	
	
	memset(vis,0,sizeof(vis));
	totalLen=0;
	minLen=1<<28;
	totalCost=0;
	vis[1]=1;
	dfs(1);
	if(minLen<(1<<28)){
		cout<<minLen<<endl;
	}
	
	
	return 0;
}