[分层图] 汽车加油行驶问题

题目描述

给定一个 $N\times N$ 的方形网格，设其左上角为起点◎，坐标为 $(1,1)$，$X$ 轴向右为正，$Y$ 轴向下为正，每个方格边长为 $1$，如图所示。

一辆汽车从起点◎出发驶向右下角终点▲，其坐标为 $(N,N)$。

在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。

汽车在行驶过程中应遵守如下规则：

1. 汽车只能沿网格边行驶，装满油后能行驶 $K$ 条网格边。出发时汽车已装满油，在起点与终点处不设油库。
2. 汽车经过一条网格边时，若其 $X$ 坐标或 $Y$ 坐标减小，则应付费用 $B$，否则免付费用。
3. 汽车在行驶过程中遇油库则应加满油并付加油费用 $A$。
4. 在需要时可在网格点处增设油库，并付增设油库费用 $C$（不含加油费用 $A$）。
5. $N,K,A,B,C$ 均为正整数，且满足约束 $2\le N\le 100,2\le K\le 10$。

设计一个算法，求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

输入格式

第一行包含五个整数 $N,K,A,B,C$。

第二行起是一个 $N\times N$ 的 $0-1$ 方阵,每行 $N$ 个值，至 $N+1$ 行结束。

方阵的第 $i$ 行第 $j$ 列处的值为 $1$ 表示在网格交叉点 $(i,j)$ 处设置了一个油库，为 $0$ 时表示未设油库。

各行相邻两个数以空格分隔。

输出格式

输出共一行，为最小费用。

样例

样例输入1：

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

样例输出1：

12

数据范围

$2\le N\le 100$
$2\le K\le 10$

题解

求最小花费，还有油量限制，考虑使用 dp 解决（分层图）。

将 $(x,y)$ 坐标油量为 $k$ 看作一个点。

接下来考虑如何转移：

假如当前点 $(x,y,k)$，首先可以消耗油量直接转移到旁边的四个点（注意向左或向上走要花费 $B$）

if(i - 1 >= 0) v[t].push_back({get(i - 1, j, K - 1), B});
if(j - 1 >= 0) v[t].push_back({get(i, j - 1, K - 1), B});
if(i + 1 < n) v[t].push_back({get(i + 1, j, K - 1), 0});
if(j + 1 < n) v[t].push_back({get(i, j + 1, K - 1), 0});

若当前点是油库，则当前点的任意油量可以连到满油量。

for(int k = 0; k < K; ++ k){
    v[get(i, j, k)].push_back({t, A + C});
}

最后跑一遍最短路，求出最小花费。

int n, K, A, B, C;
vector<pair<int, int>> v[110010];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int dis[110010];
int fl[110010];
int get(int x, int y, int k){
    return (x * n + y) * (K + 1) + k;
}
void dijkstra(int x){
    memset(dis, 0x3f, sizeof(dis));
    memset(fl, 0, sizeof(fl));
    dis[x] = 0;
    q.push({0, x});
    while(!q.empty()){
        auto t = q.top();
        q.pop();
        if(fl[t.second]) continue;
        fl[t.second] = 1;
        for(auto i : v[t.second]){
            if(dis[i.first] > dis[t.second] + i.second){
                dis[i.first] = dis[t.second] + i.second;
                q.push({dis[i.first], i.first});
            }
        }
    }
}
int main(){
    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){
            int x;
            scanf("%d", &x);
            if(x){
                int t = get(i, j, K);
                for(int k = 0; k < K; ++ k){
                    v[get(i, j, k)].push_back({t, A});
                }
                if(i - 1 >= 0) v[t].push_back({get(i - 1, j, K - 1), B});
                if(j - 1 >= 0) v[t].push_back({get(i, j - 1, K - 1), B});
                if(i + 1 < n) v[t].push_back({get(i + 1, j, K - 1), 0});
                if(j + 1 < n) v[t].push_back({get(i, j + 1, K - 1), 0});
            }
            else{
                int t = get(i, j, K);
                for(int k = 0; k < K; ++ k){
                    v[get(i, j, k)].push_back({t, A + C});
                }
                for(int k = 1; k <= K; ++ k){
                    int p = get(i, j, k);
                    if(i - 1 >= 0) v[p].push_back({get(i - 1, j, k - 1), B});
                    if(j - 1 >= 0) v[p].push_back({get(i, j - 1, k - 1), B});
                    if(i + 1 < n) v[p].push_back({get(i + 1, j, k - 1), 0});
                    if(j + 1 < n) v[p].push_back({get(i, j + 1, k - 1), 0});
                }
            }
        }
    }
    dijkstra(get(0, 0, K));
    int ans = 0x3f3f3f3f;
    for(int k = 0; k < K; ++ k){
        ans = min(ans, dis[get(n - 1, n - 1, k)]);
    }
    printf("%d", ans);
    return 0;
}