题目描述
- 编号为1-N的N座城镇用若干仅供单向行驶的道路相连，每条道路上均有两个参数：道路长度(lenth)和在该条道路上行驶的费用（cost）。
BOB准备从城镇1出发到达城镇N，但他目前只有W的钱，为此，你需要帮助他寻找一条从城镇1到城镇N在他能支付的前提下的一条最短路线。
输入格式
- W,N,M（N为城镇数目，2<=N<=100，M为道路条数，W为钱的数目
- 随后的M行每行为一条道路的信息，包含4个数值（u,v,w,cost），表示从城镇u到v有一条长度为cost的单向道路，经过这条道路需要花费 cost。（1<=u,v<=N,1<=w<=100,1<=cost<=100)
输出格式
输出最短长度，若无解，则输出“NO”；
样例
样例输入
5 6 7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
样例输出
111 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=100+10,maxm=10000+10,inf=0x3f3f3f3f; 4 int w,n,m; 5 struct Edge{ 6 int to,next,lenth,money; 7 }e[maxm]; 8 int head[maxn],tot=0; 9 void Insert(int a,int b,int c,int d){ 10 e[++tot].to=b; 11 e[tot].lenth=c; 12 e[tot].money=d; 13 e[tot].next=head[a]; 14 head[a]=tot; 15 } 16 int d[maxn][1000+10]; 17 void spfa(int x){ 18 queue< pair<int,int> > q; 19 int vis[maxn][1000+10]; 20 memset(d,0x3f,sizeof(d)); 21 memset(vis,0,sizeof(vis)); 22 q.push(make_pair(x,0)); 23 vis[x][0]=1; 24 d[x][0]=0; 25 while(!q.empty()){ 26 pair<int,int> now=q.front(); 27 q.pop(); 28 int u=now.first; 29 int s=now.second; 30 vis[u][s]=0; 31 for(int i=head[u];i;i=e[i].next){ 32 int v=e[i].to; 33 if(s+e[i].money>w) continue; 34 if(d[v][s+e[i].money]>d[u][s]+e[i].lenth){ 35 d[v][s+e[i].money]=d[u][s]+e[i].lenth; 36 if(!vis[v][s+e[i].money]){ 37 vis[v][s+e[i].money]=1; 38 q.push(make_pair(v,s+e[i].money)); 39 } 40 } 41 } 42 } 43 } 44 int main(){ 45 scanf("%d%d%d",&w,&n,&m); 46 for(int i=1;i<=m;i++){ 47 int u,v,l,cost; 48 scanf("%d%d%d%d",&u,&v,&l,&cost); 49 Insert(u,v,l,cost); 50 } 51 spfa(1); 52 int ans=inf; 53 for(int i=0;i<=w;i++){ 54 ans=min(ans,d[n][i]); 55 } 56 if(ans==inf) printf("NOn"); 57 else printf("%dn",ans); 58 return 0; 59 }
View Code
原文链接: https://www.cnblogs.com/HZOIDJ123/p/13339724.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/368499
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
