题意 ： 求从1城市到n城市的最短路。但是每条路有两个属性，一个是路长，一个是花费。要求在花费为K内，找到最短路。
思路 ：这个题好像有很多种做法，我用了BFS+优先队列。崔老师真是千年不变的SPFA啊，链接。还有一个神用了好几种方法分析，链接 。
用优先队列控制长度，保证每次加的都是最短的，每次从队列中取元素，沿着取出来的点往下找，如果费用比K少再加入队列，否则不加，这样可以省时间。
//
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue> using namespace std ; int K,N,R ;
int cnt,ans ;
int head[] ;
const int INF = ; struct node
{
int u,v ;
int len ;
int cost ;
int next ;
} st[];
struct node1
{
int len,cost,u ;
friend bool operator < (node1 a,node1 b)
{
return a.len > b.len ;
}
}; void addedge(int u,int v,int len,int cost)
{
st[cnt].u = u ;
st[cnt].v = v ;
st[cnt].len = len ;
st[cnt].cost = cost ;
st[cnt].next = head[u] ;
head[u] = cnt ++ ;
} void bfs()
{
priority_queue<node1>Q ;
struct node1 p ;
p.len = ;
p.cost = ;
p.u = ;
Q.push(p) ;
while(!Q.empty())
{
p = Q.top() ;
Q.pop() ;
if(p.u == N)
{
ans = p.len ;
break ;
//return ans ;
}
for(int i = head[p.u] ; i != - ; i = st[i].next)
{
struct node1 st1 ;
st1.u = st[i].v ;
if(p.cost + st[i].cost <= K)
{
st1.cost = p.cost+st[i].cost ;
st1.len = p.len+st[i].len ;
Q.push(st1) ;
}
}
}
}
int main()
{
int S,D,L,T ;
while(scanf("%d %d %d",&K,&N,&R) != EOF)
{
cnt = ;
memset(head,-,sizeof(head)) ;
for(int i = ; i <= R ; i++)
{
scanf("%d %d %d %d",&S,&D,&L,&T) ;
addedge(S,D,L,T) ;
}
ans = INF ;
bfs() ;
if(ans < INF) printf("%d\n",ans) ;
else printf("-1\n") ;
}
return ;
}