题意 ： 求从1城市到n城市的最短路。但是每条路有两个属性，一个是路长，一个是花费。要求在花费为K内，找到最短路。
思路 ：这个题好像有很多种做法，我用了BFS+优先队列。崔老师真是千年不变的SPFA啊，链接。还有一个神用了好几种方法分析，链接 。
用优先队列控制长度，保证每次加的都是最短的，每次从队列中取元素，沿着取出来的点往下找，如果费用比K少再加入队列，否则不加，这样可以省时间。
1 //1724 2 #include <stdio.h> 3 #include <string.h> 4 #include <iostream> 5 #include <queue> 6 7 using namespace std ; 8 9 int K,N,R ; 10 int cnt,ans ; 11 int head[10101] ; 12 const int INF = 9999999 ; 13 14 struct node 15 { 16 int u,v ; 17 int len ; 18 int cost ; 19 int next ; 20 } st[10100]; 21 struct node1 22 { 23 int len,cost,u ; 24 friend bool operator < (node1 a,node1 b) 25 { 26 return a.len > b.len ; 27 } 28 }; 29 30 void addedge(int u,int v,int len,int cost) 31 { 32 st[cnt].u = u ; 33 st[cnt].v = v ; 34 st[cnt].len = len ; 35 st[cnt].cost = cost ; 36 st[cnt].next = head[u] ; 37 head[u] = cnt ++ ; 38 } 39 40 void bfs() 41 { 42 priority_queue<node1>Q ; 43 struct node1 p ; 44 p.len = 0 ; 45 p.cost = 0 ; 46 p.u = 1 ; 47 Q.push(p) ; 48 while(!Q.empty()) 49 { 50 p = Q.top() ; 51 Q.pop() ; 52 if(p.u == N) 53 { 54 ans = p.len ; 55 break ; 56 //return ans ; 57 } 58 for(int i = head[p.u] ; i != -1 ; i = st[i].next) 59 { 60 struct node1 st1 ; 61 st1.u = st[i].v ; 62 if(p.cost + st[i].cost <= K) 63 { 64 st1.cost = p.cost+st[i].cost ; 65 st1.len = p.len+st[i].len ; 66 Q.push(st1) ; 67 } 68 } 69 } 70 } 71 int main() 72 { 73 int S,D,L,T ; 74 while(scanf("%d %d %d",&K,&N,&R) != EOF) 75 { 76 cnt = 0 ; 77 memset(head,-1,sizeof(head)) ; 78 for(int i = 1 ; i <= R ; i++) 79 { 80 scanf("%d %d %d %d",&S,&D,&L,&T) ; 81 addedge(S,D,L,T) ; 82 } 83 ans = INF ; 84 bfs() ; 85 if(ans < INF) printf("%d ",ans) ; 86 else printf("-1 ") ; 87 } 88 return 0 ; 89 }