题目描述
- 编号为1-N的N座城镇用若干仅供单向行驶的道路相连,每条道路上均有两个参数:道路长度(lenth)和在该条道路上行驶的费用(cost)。
输入格式
- 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
样例输出
11
1 #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("NO\n"); 57 else printf("%d\n",ans); 58 return 0; 59 }View Code