记录编号	288959	评测结果	AAAAAAAAAAA
题目名称	[HZOI 2016]乘车路线	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-08-03 18:03:09	内存使用	34.65 MiB

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define maxn 1000010
int a,b,c,d,head[maxn],dis[maxn],mi[maxn],mon[maxn],road[maxn],n,m,tot,totmoney;
struct Edge{
	int to,next,dis,money;
}edge[maxn];
struct Node{
	int num,money,dist;
	Node(int x=0,int y=0,int z=0){num=x,dist=y,money=z;}
	bool operator <(const Node &x)const
	{
		if(dist!=x.dist)return dist>x.dist;
		else return money<x.money;
	}
};
void Addedge(int x,int y,int z,int q)
{
	edge[++tot].to=y;
	edge[tot].dis=z;
	edge[tot].money=q;
	edge[tot].next=head[x];
	head[x]=tot;
}
void bfs(int s,int t)
{
	priority_queue<Node> q;
	q.push(Node(s,0,totmoney));
	while(!q.empty()){
		Node node=q.top();q.pop();
		int k=node.num,money=node.money;
		if(k==t){
			printf("%d\n",node.dist);return;
		}
		for(int i=head[k];i;i=edge[i].next)
		{
			int t=edge[i].to;
			if(money-edge[i].money>=0){
				q.push(Node(t,edge[i].dis+node.dist,money-edge[i].money));
			}
		}
	}
	printf("NO");return;
}
	
int main()
{
	freopen("hzoi_roads.in","r",stdin);
	freopen("hzoi_roads.out","w",stdout);
	scanf("%d%d%d",&totmoney,&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		Addedge(a,b,c,d);
	}
	bfs(1,n);
	return 0;
}