本文共 1992 字，大约阅读时间需要 6 分钟。

题目大意： 有一张网格图，起点为 $(1,1)$，终点为 $(n,n)$，汽车满油时可以走 $k$ 步，每步只能沿着网格边走，如果走到加油站则必须加满油，费用为 $A$，你也可以在任意地方新建一个加油站，费用为 $C$，走的过程中，如果 $x$ 或 $y$ 坐标减小了那么需要付出 $B$ 的费用，求出起点到终点的最小费用。

题解

众所周知，网络流24题中出现一些最短路题是很正常的。

走 $k$ 步这个限制可以通过分层图解决，建 $k+1$ 层，每层对应当前还能走多少步，然后向上下左右走的边都从当前点向下一层建。

如果走到加油站，则强制这个点走到最高层（即加满油，能走的步数为 $k$），然后加上 $A$ 的费用。要注意的是，如果此时已经在最高层，说明已经加过油了，就不需要了。

新建加油站的话就判断一下 当前位置是否能更新最高层中的对应位置 即可。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 200010int n,k,A,B,C,a[110][110];struct edge{
   int y,z,next;};edge e[maxn<<3];int first[maxn],len=0;void buildroad(int x,int y,int z){
   	e[++len]=(edge){
   y,z,first[x]};	first[x]=len;}int pos(int x,int y){
   return (x-1)*n+y;}bool oil[maxn],v[maxn];int q[maxn],st=1,ed=2,f[maxn],ans=2147483640;int f1[4]={
   -1,0,1,0};int f2[4]={
   0,-1,0,1};int main(){
   	scanf("%d %d %d %d %d",&n,&k,&A,&B,&C);	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)	{
   		scanf("%d",&a[i][j]);		if(a[i][j])for(int c=0;c<=k;c++)oil[pos(i,j)+c*n*n]=true;		int limit=(1-a[i][j])*(k-1);		for(int c=0;c<=limit;c++)		for(int l=0;l<4;l++)		{
   			int x=i+f1[l],y=j+f2[l];			if(x<1||x>n||y<1||y>n)continue;			buildroad(pos(i,j)+c*n*n,pos(x,y)+(c+1)*n*n,l<2?B:0);		}	}	memset(f,63,sizeof(f));	q[st]=1;f[1]=0;v[1]=true;	while(st!=ed)	{
   		int x=q[st++];v[x]=false;st=st>(k+1)*n*n?1:st;		if(oil[x]&&x>n*n)		{
   			if(f[(x-1)%(n*n)+1]>f[x]+A)			{
   				f[(x-1)%(n*n)+1]=f[x]+A;				if(!v[(x-1)%(n*n)+1])v[q[ed++]=(x-1)%(n*n)+1]=true,ed=ed>(k+1)*n*n?1:ed;			}			continue;		}		if(!oil[x]&&x>n*n)		{
   			if(f[(x-1)%(n*n)+1]>f[x]+A+C)			{
   				f[(x-1)%(n*n)+1]=f[x]+A+C;				if(!v[(x-1)%(n*n)+1])v[q[ed++]=(x-1)%(n*n)+1]=true,ed=ed>(k+1)*n*n?1:ed;			}		}		for(int i=first[x];i;i=e[i].next)		{
   			int y=e[i].y;			if(f[y]>f[x]+e[i].z)			{
   				f[y]=f[x]+e[i].z;				if(!v[y])v[q[ed++]=y]=true,ed=ed>(k+1)*n*n?1:ed;			}		}	}	for(int c=0;c<=k;c++)ans=min(ans,f[(c+1)*n*n]);	printf("%d",ans);}
     
    
   

转载地址：http://cjnib.baihongyu.com/