题意：有向图，给你m条边，每条边有两个权值，路径长和通过这条路径的花费，问你在不超过k花费的前提下，最短的路径从1走到n
解题思路：因为边数很少，我们可以直接用暴力每条边的方式来找最小的路径长，也就是用一个优先队列，每次弹出路径最短的边，计算当前花费和下条边的花费如果小于k，那么这条边就可行。
很多博客写是迪杰斯特拉+heap，我觉得没有松弛过程的应该算不上单元最短路的写法把（QAQ）;
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define maxn 100000
#define inf 1e9
using namespace std;
struct Edge
{
int next;
int to;
int w;
int c;
}edge[maxn];
struct node
{
int num;
int dist;
int cost;
node(int _num=0,int _dist=0,int _cost=0):num(_num),dist(_dist),cost(_cost){}
bool operator < (const node &a) const
{
return a.dist<dist;
}};
int head[maxn];
int cnt;
int dist[maxn];
int k,n,m;
void add(int u,int v,int w,int c)
{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].c=c;
edge[cnt].next=head[u];
head[u]=cnt++;}
int dij(int x)
{
int ans=-1;
node u,v;
priority_queue<node>que;
que.push(node(x,0,0));
while(!que.empty())
{
node u=que.top();
que.pop();
int now=u.num;
if(now==n)
{
ans=u.dist;
return ans;
break;
}
for(int i=head[now];i!=-1;i=edge[i].next)
{
if(u.cost+edge[i].c<=k)
{
v.num=edge[i].to;
v.dist=u.dist+edge[i].w;
v.cost=u.cost+edge[i].c;
que.push(v);
}
}
}
return ans;
}
int main()
{
int x,y,w,c; while(cin>>k>>n>>m)
{
memset(head,-1,sizeof(head));
cnt=0;
for(int i=1;i<=m;i++)
{
cin>>x>>y>>w>>c;
add(x,y,w,c);
}
cout<<dij(1)<<endl;
}}
