记录编号	350912	评测结果	AAAAAAAAAAA
题目名称	[HZOI 2016]乘车路线	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2016-11-16 07:43:35	内存使用	6.80 MiB

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define Begin freopen("hzoi_roads.in","r",stdin);freopen("hzoi_roads.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
const int maxn=100000+20;
struct Node{
	int num,dis,cost;
	Node(){};
	Node(int a,int b,int c){num=a;dis=b;cost=c;}
	bool operator < (const Node & a)const{
		return dis>a.dis;
	} 
};
struct Edge{
	int next,to,dis,cost;
}e[maxn<<2];
int n,m,tot,len,head[maxn];
void Insert(int x,int y,int z,int cost){
	len++;e[len].to=y;e[len].next=head[x];e[len].dis=z;e[len].cost=cost;head[x]=len;
}
void Init();
void Dijs(int x){
	priority_queue<Node> q;q.push(Node(x,0,0));
	while(!q.empty()){
		Node temp=q.top();q.pop();
		int k=temp.num;
		if(k==n){printf("%d\n",temp.dis);return;}
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(temp.cost+e[i].cost<=tot){
				q.push(Node(j,temp.dis+e[i].dis,temp.cost+e[i].cost));
			}
		}
	}
	puts("NO");
}
int main(){
    Begin;
    Init();
    getchar();getchar();
    End;
    return 0;
}
void Init(){
	scanf("%d%d%d",&tot,&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z,cost;scanf("%d%d%d%d",&x,&y,&z,&cost);
		Insert(x,y,z,cost);
	}
	Dijs(1);
}