新一波新冠病毒疫情最新消息_免费制作电子相册的软件_百度seo是什么意思呢_seo手机端排名软件

题目描述

给定一个 $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;
}