记录编号	153861	评测结果	AAAAAAAA
题目名称	[网络流24题] 汽车加油行驶	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.111 s
提交时间	2015-03-19 18:06:04	内存使用	8.67 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int N=120010,INF=1e9;
int n,nn,k,a,b,c,i,p,j,zj1,zj2,ST,ans;

int to[N*5]={0},ne[N*5]={0},w[N*5]={0},head[N]={0},sj=0;
inline void addedge(int u,int v,int W)
{to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=W;}

/*---------------------------------------------------------*/
int que[N],qhead=1,qtail=120009;bool flag[N]={0};
inline int GET_fr()
{int x=que[qhead];que[0]--,flag[x]=0;if(++qhead==N)qhead=1;return x;}
inline void PUSH_fr(int x)
{flag[x]=1,que[0]++;if(!(--qhead))qhead=120009;que[qhead]=x;}
inline void PUSH_be(int x)
{flag[x]=1,que[0]++;if(++qtail==N)qtail=1;que[qtail]=x;}
/*---------------------------------------------------------*/
void init()
{
	scanf("%d%d%d%d%d",&n,&k,&a,&b,&c);nn=n*n;
	for(i=0;i<n;i++)for(p=1;p<=n;p++)
	{
		scanf("%d",&zj1);
		if(zj1)
		{
			zj1=i*n+p;
			for(j=0;j<k;j++)addedge(zj1+nn*j,zj1+nn*k,a);
			zj1+=nn*k;
			if(p<n)addedge(zj1,zj1-nn+1,0);
			if(i<n-1)addedge(zj1,zj1-nn+n,0);
			if(p>1)addedge(zj1,zj1-nn-1,b);
			if(i>0)addedge(zj1,zj1-nn-n,b);
		}
		else
		{
			zj1=i*n+p;
			for(j=0;j<k;j++)
			addedge(zj1+nn*j,zj1+nn*k,a+c);
			for(j=1;j<=k;j++)
			{
				if(p<n)addedge(zj1+nn*j,zj1+nn*(j-1)+1,0);
				if(i<n-1)addedge(zj1+nn*j,zj1+nn*(j-1)+n,0);
				if(p>1)addedge(zj1+nn*j,zj1+nn*(j-1)-1,b);
				if(i>0)addedge(zj1+nn*j,zj1+nn*(j-1)-n,b);
			}
		}
	}
}
int dis[N]={0};
void spfa()
{
	ST=nn*k+1;zj1=nn*(k+1);
	for(i=1;i<=zj1;i++)dis[i]=INF;
	dis[ST]=0;PUSH_be(ST);
	while(que[0])
	for(zj1=GET_fr(),i=head[zj1];i;i=ne[i])
	if(dis[to[i]]>(zj2=dis[zj1]+w[i]))
	{
		dis[to[i]]=zj2;if(!flag[to[i]])
		if(que[0]&&zj2<=dis[que[qhead]])PUSH_fr(to[i]);
		else PUSH_be(to[i]);
	}
	zj1=nn;ans=INF;
	for(i=0;i<=k;i++)
	if(dis[zj1+nn*i]<ans)ans=dis[zj1+nn*i];
}
int main()
{
	freopen("trav.in","r",stdin);
	freopen("trav.out","w",stdout);
	init();
	spfa();
	printf("%d\n",ans);
	return 0;
}