POJ 1724 ROADS(制限条件付き最短、深読み)

図の中ですべての道はすべて道の長さと“通行料”の2つのパラメータがあって、今K元だけあって、起点から終点までの最短ルートを求めて、つまりKの費用の内の最短ルートです.
この問題は実は多くの解があるが,問題記述用のモデルが最短のモデルにすぎず,その方法は多種多様である.
深搜解:毎回費用の制限を満たす点を探して操作します;総路が長くなると遡る.再帰出口はゴールを見つけることです.

#include<cstdio>
#include<cstring>
const int N = 1010;
const int INF = 1e6;

struct Edge{
	int s,e,len,cost;
	int next;
}edge[10*N];

int n,m,e_num,head[N],vis[N];
int ans;

void AddEdge(int a,int b,int c,int d){
	edge[e_num].s=a; edge[e_num].e=b; edge[e_num].len=c; edge[e_num].cost=d;
	edge[e_num].next=head[a]; head[a]=e_num++;
}

void dfs(int id,int dist,int money){//      ,         ,     
	if(dist>ans)return;//        ,  
	if(id==n && money>=0 && dist<ans) ans=dist;//      
	for(int i=head[id];i!=-1;i=edge[i].next){
		int u=edge[i].e;
		if(!vis[u] && money >= edge[i].cost){
			vis[u]=1;
			dfs(u,dist+edge[i].len,money-edge[i].cost);
			vis[u]=0;
		}
	}
}

int main()
{
	int i,a,b,c,d,k;
	while(~scanf("%d%d%d",&k,&n,&m))
	{
		e_num=0;
		memset(head,-1,sizeof(head));
		for(i=0;i<m;i++){
			scanf("%d%d%d%d",&a,&b,&c,&d);
			AddEdge(a,b,c,d);
		}
		ans=INF;
		memset(vis,0,sizeof(vis));
		dfs(1,0,k);
		printf(ans<INF?"%d
":"-1
",ans);
	}
	return 0;
}

dij+heap解:最も近い費用制限を満たすポイントをキューに入れる

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int N = 105;
const int INF = 1e6;

struct node
{
	int id,cost,dis;
	bool operator < (const node &a) const
	{
		return a.dis<dis;
	}
};

struct Edge{
	int e,len,cost;
	int next;
}edge[10005];

int n,k,e_num,head[N];

void AddEdge(int a,int b,int c,int d){
	edge[e_num].e=b; edge[e_num].len=c; edge[e_num].cost=d;
	edge[e_num].next=head[a]; head[a]=e_num++;
}

void dij(){
	int i;
	node cur,next;
	priority_queue <node> q;
	
	cur.id=1; cur.dis=0; cur.cost=0;
	q.push(cur);
	
	int ans=INF;
	while(!q.empty()){
		cur=q.top();//       
		q.pop();
		if(cur.id==n){
			ans=cur.dis;break;
		}
		
		for(i=head[cur.id];i!=-1;i=edge[i].next){
			if(cur.cost+edge[i].cost<=k){//             
				next.id=edge[i].e;
				next.dis=edge[i].len+cur.dis;
				next.cost=edge[i].cost+cur.cost;
				q.push(next);
			}
		}
	}
	printf(ans<INF?"%d
":"-1
",ans);
}

int main()
{
	int a,b,c,d,m;
	while(~scanf("%d%d%d",&k,&n,&m))
	{
		e_num=0;
		memset(head,-1,sizeof(head));
		while(m--){
			scanf("%d%d%d%d",&a,&b,&c,&d);
			AddEdge(a,b,c,d);
		}
		dij();
	}
	return 0;
}