题目大意： 给你K元钱，给你n个点，m条边，和每条边的长度，和用的钱 在钱不超出的情况下求最短路
比一般的最短路多了一点限制，就是有钱数的限制！！！！
那么我们就要把所有的情况全部列出来了
本来这题用搜索写，找出所有情况就ok
但是这里用一种更为巧妙的办法
具体思想从三进制状态压缩这道题里的一个思想继承过来的
#include <iostream> #include<stdio.h> #include<string.h> #include<string> #include<algorithm> #include<stdlib.h> #include<queue> #define mem(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f using namespace std; int n,m,k; struct node { int num,dis,cost; bool friend operator < (node a,node b) { return a.dis>b.dis; //从小到大排列 } }; int dis[105][10005]; int u[10005],v[10005],w[10005],c[10005]; int first[105],nex[10005]; void spfa() { for(int i=1;i<=n;i++) //初始化 { for(int j=0;j<=k;j++) { dis[i][j]=inf; } } dis[1][0]=0; priority_queue<node>q;//优先队列，路径小的先来 node a,b; a.num=1; a.cost=0; a.dis=0; q.push(a); while(!q.empty()) { a=q.top(); q.pop(); if(a.num==n)//如果找到这个点就输出 { printf("%d\n",a.dis); return; } for(int i=first[a.num];i!=-1;i=nex[i])//遍历邻接表 { int cost=a.cost+c[i]; if(cost>k)continue;//如果花费的钱超出了，那么次情况跳出 if(dis[v[i]][cost]>a.dis+w[i])//如果花出的钱没超，并且可以松弛 { dis[v[i]][cost]=a.dis+w[i]; b.num=v[i]; b.cost=cost; b.dis=dis[v[i]][cost]; q.push(b); } } } printf("-1\n"); } int main() { while(~scanf("%d",&k)) { scanf("%d",&n); scanf("%d",&m); mem(first,-1); for(int i=0;i<m;i++) { scanf("%d%d%d%d",&u[i],&v[i],&w[i],&c[i]); nex[i]=first[u[i]];//建立邻接表 first[u[i]]=i; } spfa(); } return 0; }
