Description：

一个 $n\times n$ 的网格图，一辆车从左上角开到右下角，刚开始油箱是满的，一个满的油箱可以跑 $k$ 条边，有些位置有加油站，到了加油站强制花 $a$ 元加满油，往东或往南走不花钱，往西或往北走一格 $b$ 元，可以建加油站，花费 $c$ 元且不包括加油的 $a$ 元，问最小花费。

$1\le n \le 100,1\le k \le 10$

Solution：

建一个 $k+1$ 层的图，对于行驶直接从上层到下层连相应花费的边，对于加油站的点，不连行驶的边，把所有层中这个点全部连向第一层中这个点，边权为 $a$ ，在第一层向第二层连行驶的边，对于建加油站，从每层这个点向第一层中这个点连边权为 $a+c$ 的边，最后跑最短路即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,t,A,B,C;

#define MAXN 110

#define MAXK 11

struct edge

{

    int to,nxt,v;

}e[MAXN * MAXN * MAXK * 4 + MAXN * MAXN * MAXK];

int edgenum = 0;

int lin[MAXN * MAXN * MAXK] = {0};

void add(int a,int b,int c)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    return;

}

int p[MAXN][MAXN];

int to(int i,int j){return (i - 1) * n + j;}

int d[MAXN * MAXN * MAXK];

bool v[MAXN * MAXN * MAXK];

int main()

{

    scanf("%d%d%d%d%d",&n,&t,&A,&B,&C);

    for(int i = 1;i <= n;++i)

        for(int j = 1;j <= n;++j)

            scanf("%d",&p[i][j]);

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j <= n;++j)

        {

            if(p[i][j] == 0)

            {

                for(int k = 0;k < t;++k)

                {

                    if(i > 1)add(k * n * n + to(i,j),(k + 1) * n * n + to(i - 1,j),B);

                    if(j > 1)add(k * n * n + to(i,j),(k + 1) * n * n + to(i,j - 1),B);

                    if(i < n)add(k * n * n + to(i,j),(k + 1) * n * n + to(i + 1,j),0);

                    if(j < n)add(k * n * n + to(i,j),(k + 1) * n * n + to(i,j + 1),0);

                }

                for(int k = 0;k <= t;++k)add(k * n * n + to(i,j),to(i,j),C + A);

            }

            else

            {

                for(int k = 0;k <= t;++k)add(k * n * n + to(i,j),to(i,j),A);

                if(i > 1)add(to(i,j),n * n + to(i - 1,j),B);

                if(j > 1)add(to(i,j),n * n + to(i,j - 1),B);

                if(i < n)add(to(i,j),n * n + to(i + 1,j),0);

                if(j < n)add(to(i,j),n * n + to(i,j + 1),0);

            }

        }

    }

    queue<int> q;q.push(1);

    memset(d,0x3f,sizeof(d));

    memset(v,false,sizeof(v));

    d[1] = 0;v[1] = true;

    while(!q.empty())

    {

        int k = q.front();q.pop();

        v[k] = false;

        for(int i = lin[k];i != 0;i = e[i].nxt)

        {

            if(d[e[i].to] > d[k] + e[i].v)

            {

                d[e[i].to] = d[k] + e[i].v;

                if(!v[e[i].to])

                {

                    v[e[i].to] = true;

                    q.push(e[i].to);

                }

            }

        }

    }

    int ans = 0x3f3f3f3f;

    for(int i = 0;i <= t;++i)

    {

        ans = min(ans,d[i * n * n + to(n,n)]);

    }

    cout << ans << endl;

    return 0;

}