P4009 求调，36pts

#include <bits/stdc++.h>

using namespace std;

const int N = 105,K = 15;
int n,k,a,b,c;
int dx[5] = {-1,0,0,1};
int dy[5] = {0,-1,1,0};
bool d[N][N];
int dis[N][N][K];
bool vis[N][N][K];
struct node{int x,y,f;};
queue <node>q;
void spfa()
{
	memset(dis,0x3f,sizeof dis);
	dis[1][1][k] = 0;
	vis[1][1][k] = 1;
	q.push({1,1,k});
	while(!q.empty())
	{
		int x = q.front().x;
		int y = q.front().y;
		int f = q.front().f;
		q.pop();
		if(f == 0) continue;
	//	cout << x << " " << y << " " << f << " " << dis[x][y][f] << endl;
		vis[x][y][f] = 1;
		for(int i = 0;i < 4;i++)
		{
			int p = 0;
			int x_new = x + dx[i];
			int y_new = y + dy[i];
			if(x_new > n || y_new > n || x_new < 1 || y_new < 1) continue;
			if(i < 2) p += b;
			if(d[x_new][y_new] == 0 && dis[x_new][y_new][f - 1] > dis[x][y][f] + p)
			{
				dis[x_new][y_new][f - 1] = dis[x][y][f] + p;
				if(vis[x_new][y_new][f - 1] == 0)
				{
					q.push({x_new,y_new,f - 1});
				}
			}
			p += a;
			if(d[x_new][y_new] == 0 && f == 1)
			{
				p += c;
			}
			if((d[x_new][y_new] == 1 || f == 1) && dis[x_new][y_new][k] > dis[x][y][f] + p)
			{
				dis[x_new][y_new][k] = dis[x][y][f] + p;
				if(vis[x_new][y_new][k] == 0)
				{
					q.push({x_new,y_new,k});
				}
			}
		}
	}
}
int main()
{
	cin >> n >> k >> a >> b >> c;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			cin >> d[i][j];
		}
	}
	spfa();
	int ans = 0x3f3f3f3f;
	for(int i = 0;i < k;i++)
	{
		ans = min(ans,dis[n][n][i]);
	}
	cout << ans;
}