题意：有R条路，每条路都有一定的路长和花费，问在总的花费小于一定的值的情况下，从1到N的最短路程
注意：这里两点之间单向边，且可能存在很多条路，所以只能用邻接表存储。
思路：用dijkstra，但是每次判断一个元素是否能进入队列，并不是源点到它的距离被更新了才入队，
而是只要满足从源点到该点总的路费小于给定的值，都可入队。
每次从优先级队列中取出路程最小（如果路程相同，取花费最小）的点。
当N点被取出来时，直接结束
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
using namespace std;
const int maxn=0x3f3f3f3f; int money,n,r,a,b,l,toll,t;
int ans,tot; struct Road{
int next,from,to; }road[]; int head[];
int rlength[]; //每条路的路长
int cost[]; //每条路的花费 struct State{
//u到1点的总的花费(cost)、路长(dis)
int u;
int cost,dis;
void init(int uu,int costt,int diss){
u=uu;
cost=costt;
dis=diss;
} bool operator < (const State tmp) const
{
if(dis==tmp.dis)
return cost>tmp.cost;
else
return dis>tmp.dis;
//如果dis<tmp.dis,则为从小到大排，但这样的话优先级队列取得是最大的，它默认的就是最大堆,取排在最后的
}
}; void add(int a,int b,int ll,int tt){
road[tot].next=head[a];
road[tot].from=a;
road[tot].to=b;
rlength[tot]=ll;
cost[tot]=tt;
head[a]=tot++;
} void dijastra(){
int idx;
State temp,minNode,node;
priority_queue<State> q;
while(!q.empty()) q.pop();
//dis[1]=0;
//vis[1]=1;
temp.init(,,);
q.push(temp);
while(!q.empty()){
minNode=q.top();
q.pop();
idx=minNode.u;
if(idx==n){
ans=minNode.dis;
break;
}
for(int k=head[idx];k!=-;k=road[k].next){
int v=road[k].to;
if(minNode.cost+cost[k]<=money){
node.init(v,minNode.cost+cost[k],minNode.dis+rlength[k]);
q.push(node);
}
}
}
} int main()
{
scanf("%d",&t);
for(int i=;i<=t;i++){
ans=maxn;
tot=;
memset(head,-,sizeof(head)); scanf("%d",&money);
scanf("%d",&n);
scanf("%d",&r); for(int i=;i<=r;i++){
scanf("%d%d%d%d",&a,&b,&l,&toll);
add(a,b,l,toll);
}
dijastra();
if(ans==maxn)
printf("-1\n");
else
printf("%d\n",ans);
}
return ;
}