记录编号	360348	评测结果	AAAAAAAA
题目名称	[网络流24题] 汽车加油行驶	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2016-12-29 13:57:57	内存使用	1.51 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue> 
using namespace std;
const int N=110; 
int n,k,a,b,c,flag[N][N],dp[N][N][20];
bool vis[N][N][20];
struct sit{
	int x,y,K,d;
	sit(int X=0,int Y=0,int k=0){x=X;y=Y;K=k;d=dp[x][y][k];}
	bool operator > (const sit &x)const{return d>x.d;}
};
priority_queue<sit,vector<sit>,greater<sit> > Q;
void check(int x,int y,int k,int v){
	if (dp[x][y][k]>v)
		dp[x][y][k]=v,Q.push(sit(x,y,k));
}
int main()
{
	freopen("trav.in","r",stdin);
	freopen("trav.out","w",stdout); 
	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",&flag[i][j]);
	memset(dp,0x3f,sizeof dp);
	dp[1][1][k]=0;
	Q.push(sit(1,1,k));
	while (!Q.empty()){
		sit now=Q.top();Q.pop();
		int x=now.x,y=now.y,K=now.K,v=dp[x][y][K];
		if (vis[x][y][K]) continue;
		vis[x][y][K]=1;
		check(x,y,k,v+a+c);//原地加油站 
		if (K==0) continue;
		//向四个方向行进 
		if (x>1){
			if (flag[x-1][y]) check(x-1,y,k,v+a+b);
				else check(x-1,y,K-1,v+b);
		}
		if (y>1){
			if (flag[x][y-1]) check(x,y-1,k,v+a+b);
				else check(x,y-1,K-1,v+b);
		}
		if (x<n){
			if (flag[x+1][y]) check(x+1,y,k,v+a);
				else check(x+1,y,K-1,v);
		}
		if (y<n){
			if (flag[x][y+1]) check(x,y+1,k,v+a);
				else check(x,y+1,K-1,v);
		}
	}
	int ans=dp[n][n][0];
	for (int i=1;i<=k;i++) ans=min(ans,dp[n][n][i]);
	printf("%d\n",ans);
	return 0;
}