POJ 1724 最短路费用限制

迪杰斯塔拉裸题

最大花费

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 intusing 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;}