poj 3635 Full Tank 动态规划思想在spfa算法中的应用
题意:
有n个城市,和m条已知长度的路,在路上走1单位距离要花1单位油,每个城市都可以加油且有各自的油价,现在任给两个城市s,t,要求从s到t最少花多少油。
思路:
网上大多数都是拿优先队列做的,拿spfa做更有意思,但一般的spfa会超时。dis[i][j]表示到城市i时油箱里有j单位油时的最小花费。对于城市x,y,他们的距离为w,如果存在dis[x][j]<dis[y][i-w],则确定对y进行更新,注意如果对每个dis[x][j]<dis[y][j-w],dis[x][j+1]<dis[y][j-w+1]...都跟新dis[y][m],dis[y][m+1]...dis[y][c]的话会超时,需要用动态规划的思想在确定对y进行更新后只总的更新一次,具体的见代码注释部分。
代码:
#include <iostream> #include <queue> using namespace std; const int maxN=1024; const int maxM=10024; const int maxC=128; struct Edge { int v,w,next; }edge[maxM*2]; int price[maxN]; int head[maxN]; int inq[maxN]; int dis[maxN][maxC]; int n,m,e; void spfa(int c,int s,int t){ int i,j; queue<int> Q; memset(inq,0,sizeof(inq)); for(i=0;i<n;++i) for(j=0;j<=c;++j) dis[i][j]=INT_MAX; for(j=0;j<=c;++j) dis[s][j]=price[s]*j; inq[s]=1; Q.push(s); while(!Q.empty()){ int u=Q.front(); Q.pop(); inq[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v,w=edge[i].w; int flag=0; for(int j=w;j<=c;++j) if(dis[u][j]<dis[v][j-w]){ dis[v][j-w]=dis[u][j]; flag=1; } if(flag==1){ for(int j=1;j<=c;++j)//用动态规划的思想只更新一次 dis[v][j]=min(dis[v][j],dis[v][j-1]+price[v]); if(inq[v]==0){ inq[v]=1; Q.push(v); } } } /*超时代码: for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v,w=edge[i].w; int flag=0; for(int j=w;j<=c;++j) if(dis[u][j]<dis[v][j-w]){ dis[v][j-w]=dis[u][j]; for(int k=j-w;k<=c;++k)//每次都尝试到更新到加满 dis[v][k]=min(dis[v][k],dis[v][j-w]+(k-(j-w))*price[v]); flag=1; } if(flag==1&&inq[v]==0){ inq[v]=1; Q.push(v); } } */ } int ans=INT_MAX; for(i=0;i<=c;++i) ans=min(ans,dis[t][i]); if(ans==INT_MAX) printf("impossible\n"); else printf("%d\n",ans); return ; } int main() { e=0; memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); int i; for(i=0;i<n;++i) scanf("%d",&price[i]); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); edge[e].v=v;edge[e].w=w;edge[e].next=head[u]; head[u]=e++; edge[e].v=u;edge[e].w=w;edge[e].next=head[v]; head[v]=e++; } int q,c,s,t; scanf("%d",&q); while(q--){ scanf("%d%d%d",&c,&s,&t); spfa(c,s,t); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。