题意：给你k块钱、代表你的最大花费，然后N个城市，R条路，每条路给出 S，D代表城市S和D，L代表两个城市之间的距离，T代表两个城市之间去或者来的花费，问在不超过k块钱从1到n城市的最短路径
思路：Dijkstra+优先队列，只有当花费不大于k的点才放进队列里面去、优先队列按距离从小到大排队、那么每次取到的都是最小值，当点为n的时候就可以输出答案了
1 #include<cstdio> 2 #include<cmath> 3 #include<queue> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 const int qq=110; 8 const int MAX=1e6; 9 int n,m,cost,top; 10 struct State 11 { 12 int n,d,c; 13 bool operator < (const struct State a) const 14 { 15 if(a.d==d) return a.c<c; 16 return a.d<d; 17 } 18 }; 19 struct edge 20 { 21 int u,v,w,c,next; 22 }e[qq<<7]; //要注意边的数量、不要少了 23 int head[qq]; 24 void add(int u,int v,int w,int c) 25 { 26 e[top].u=u;e[top].v=v;e[top].w=w;e[top].c=c; 27 e[top].next=head[u];head[u]=top++; 28 } 29 void dijkstra() 30 { 31 priority_queue<State>q; 32 State sta; 33 int res=MAX; 34 while(!q.empty()) q.pop(); 35 sta.d = 0; 36 sta.n = 1; 37 sta.c = 0; 38 q.push(sta); 39 while(!q.empty()){ 40 State x,y; 41 int u,v,w,d,c; 42 x=q.top();q.pop(); 43 u=x.n;d=x.d; 44 if(u==n){ //判断是否出现点n、 45 res=x.d; 46 break; 47 } 48 for(int k=head[u];k!=-1;k=e[k].next){ 49 v=e[k].v;w=e[k].w;c=e[k].c; 50 if(x.c+c<=cost){ //满足条件就放进队列里面、 51 y.n=v;y.d=d+w;y.c=x.c+c; 52 q.push(y); 53 } 54 } 55 } 56 if(res==MAX) printf("-1 "); 57 else printf("%d ",res); 58 59 } 60 int main() 61 { 62 scanf("%d%d%d",&cost,&n,&m); 63 memset(head,-1,sizeof(head)); 64 top=0; 65 while(m--){ 66 int u,v,w,c; 67 scanf("%d%d%d%d",&u,&v,&w,&c); 68 add(u,v,w,c); //加边、 69 } 70 dijkstra(); 71 return 0; 72 }