题目

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 5005, M = N * N;

int n, k, a, b, c, cnt;
int g[N][N];
int h[10000005], w[10000005], e[100000005], ne[100000005], idx, num[105][105][105];
int dis[N], st[N];
queue<int> q;

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool check(int x, int y)
{
	if (x <= n && x >= 1 && y >= 1 && y <= n)  return true;
	else return false;
}

void spfa(int u)
{
	memset(dis,0x3f,sizeof(dis));
	dis[u]=0;
	st[u]=1;
	q.push(u);
	while (!q.empty())
	{
		int t=q.front();
		q.pop();
		st[t]=0;
		for (int i=h[t];~i;i=ne[i])
		{
			int j=e[i];
			if (dis[j]>dis[t]+w[i])
			{
				dis[j]=dis[t]+w[i];
				if (!st[j])
				{
					q.push(j);
					st[j]=1;
				}
			}
		}
	}
}

int main()
{
	memset(h, -1, sizeof h);
	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", &g[i][j]);
	
	for (int p = 0; p <= k; p ++ )
	  for (int i = 1; i <= n; i ++ )
	    for (int j = 1; j <= n; j ++ )
	      num[i][j][p] =  ++ cnt;
	
	for (int i = 1; i <= n; i ++ )
	  for (int j = 1; j <= n; j ++ )
	  {
	  	if (check(i + 1, j))  add(num[i][j][0], num[i + 1][j][1], 0);
	  	if (check(i, j + 1))  add(num[i][j][0], num[i][j + 1][1], 0);
	  	if (check(i - 1, j))  add(num[i][j][0], num[i - 1][j][1], b);
		if (check(i, j - 1))  add(num[i][j][0], num[i][j - 1][1], b); 
	  	
	  }
	
	for (int kk = 1; kk < k; kk ++ )
	  for (int i = 1; i <= n; i ++ )
	    for (int j = 1; j <= n; j ++ )
	      if (!g[i][j])
	      {
	      	if (check(i + 1, j))  add(num[i][j][kk], num[i + 1][j][kk + 1], 0);
	      	if (check(i, j + 1))  add(num[i][j][kk], num[i][j + 1][kk + 1], 0);
	      	if (check(i - 1, j))  add(num[i][j][kk], num[i - 1][j][kk + 1], b);
	      	if (check(i, j - 1))  add(num[i][j][kk], num[i][j - 1][kk + 1], b);
	      	add(num[i][j][kk], num[i][j][0], a + c);
	      }
	      else add(num[i][j][kk], num[i][j][0], a);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(!g[i][j])  add(num[i][j][k],num[i][j][0],c+a);  
    else  add(num[i][j][k],num[i][j][0],a);
      
    spfa(num[1][1][0]);
    int ans=2147483647;
    for(int i=0;i<=k;i++)ans=min(ans,dis[num[n][n][i]]); 
    printf("%d\n",ans);
}