题目描述

一个 $N \times N$ 的网格图，从左上角走到右下角求最小花费

出发时为满油 $K$，每次只能向上下左右移动一格同时消耗 $1$ 油量

向右下方走时无额外花费，向左上方走时额外花费$B$

有的格点有加油站，有的格点没有，当遇到加油站时必须加满油，加油花费为 $A$

没有加油站的地方可以建造加油站，建造加油站花费为 $C$

$N \leq 100$， $K \leq 10$

输入样例

9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0

输出样例

12

Dijkstra

建图，最短路

由于遇到加油站时必须加满油
所以未满油的状态向满油的状态连一条权重是 $A$ 的边，满油的再向四个方向的点连边

没有加油站的地方
未满油的状态向满油的状态连一条权重是 $A + C$ 的边
油不为 $0$ 即可向周围四个方向连边

时间复杂度 $O((n + m)log(m))$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 110010, M = N * 50, INF = 0x3f3f3f3f;

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

int n, K, A, B, C;
int v[110][110];

int get(int i, int j, int k)
{
    return (i * n + j) * (K + 1) + k;
}

int d[N];
bool st[N];

int dijkstra(int u)
{
    memset(d, 0x3f, sizeof d);
    d[u] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, u});

    while(heap.size())
    {
        int u = heap.top().second;  heap.pop();

        if(st[u])  continue;
        st[u] = true;

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i], dist = d[u] + w[i];
            if(dist < d[j])
            {
                d[j] = dist;
                heap.push({d[j], j});
            }
        }
    }

    int res = INF;
    for(int k = 0; k < K; k ++)  res = min(res, d[get(n - 1, n - 1, k)]);
    return res;
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d%d%d%d", &n, &K, &A, &B, &C);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
        {
            scanf("%d", &v[i][j]);
            if(v[i][j])
            {
                int b = get(i, j, K);
                for(int k = 0; k < K; k ++)
                {
                    int a = get(i, j, k);
                    add(a, b, A);
                }
                if(i + 1 < n)  add(b, get(i + 1, j, K - 1), 0);
                if(j + 1 < n)  add(b, get(i, j + 1, K - 1), 0);
                if(i - 1 >= 0)  add(b, get(i - 1, j, K - 1), B);
                if(j - 1 >= 0)  add(b, get(i, j - 1, K - 1), B);
            }
            else
            {
                int b = get(i, j, K);
                for(int k = 0; k < K; k ++)
                {
                    int a = get(i, j, k);
                    add(a, b, A + C);
                }
                for(int k = 1; k <= K; k ++)
                {
                    int a = get(i, j, k);
                    if(i + 1 < n)  add(a, get(i + 1, j, k - 1), 0);
                    if(j + 1 < n)  add(a, get(i, j + 1, k - 1), 0);
                    if(i - 1 >= 0)  add(a, get(i - 1, j, k - 1), B);
                    if(j - 1 >= 0)  add(a, get(i, j - 1, k - 1), B);
                }
            }
        }

    printf("%d\n", dijkstra(get(0, 0, K)));
    return 0;
}