迪杰斯塔拉裸题

最大花费

n个点

m条有向边

起点终点 路径长度 路径花费

问：在花费限制下，最短路径的长度

#include <iostream>

#include <string>

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cctype>

#include <queue>

#include <stdlib.h>

#include <cstdlib>

#include <math.h>

#include <set>

#include <vector>

#define inf 107374182

#define N 101

#define M 10001

#define ll int

using namespace std;

inline ll Max(ll a,ll b){return a>b?a:b;}

inline ll Min(ll a,ll b){return a<b?a:b;}

struct Edge{

	int f,t,d,w;

	int nex;

}edge[M];

int head[N],edgenum;

void addedge(int u,int v,int d,int w){

	Edge E={u,v,d,w,head[u]};

	edge[edgenum]=E;

	head[u]=edgenum++;

}

struct node{

	int to,dd,use;

	node(int a=0,int c=0,int b=0):to(a),dd(c),use(b){}

	bool operator<(const node&a)const{

		if(a.dd==dd)return a.use<use;

		return a.dd<dd;

	}

};

int n,maxcost,dis[N];

void spfa(int s,int e){

	int i;

	for(i=1;i<=n;i++)dis[i]=inf;

	dis[s]=0;

	priority_queue<node>q; while(!q.empty())q.pop();

	q.push(node(s,0,0));

	while(!q.empty())

	{

		node temp=q.top(); q.pop();

		int u=temp.to,nowcost=temp.use,d=temp.dd;

		if(u==e)return;

		for(i=head[u];i!=-1;i=edge[i].nex)

		{

			int v=edge[i].t;

			if(nowcost+edge[i].w<=maxcost)

			{

				if(dis[v]>d+edge[i].d)

				dis[v]=d+edge[i].d;

				q.push(node(v,d+edge[i].d,nowcost+edge[i].w));

			}

		}

	}

}

int main()

{

	int i,m,u,v,d,w;

	while(~scanf("%d",&maxcost)){

		scanf("%d%d",&n,&m);

		memset(head,-1,sizeof(head));	edgenum=0;

		while(m--){

			scanf("%d %d %d %d",&u,&v,&d,&w);

			addedge(u,v,d,w);

		}

		spfa(1,n);

		if(dis[n]==inf)dis[n]=-1;

		printf("%d\n",dis[n]);

	}

	return 0;

}