P4009 汽车加油行驶问题 - 分层图最短路

题目

题目描述

给定一个 $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\leq N\leq 100,2 \leq K \leq 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 \leq n \leq 100,2 \leq k \leq 10$

题解

这道题一开始分层图的建立着实没有想出来，甚至看了题解都没想出来（我，菜）。所以特此记录。其实是这样的，因为一辆车总共只有$k$格油，所以我们可以建立$k + 1$层图，第$i$层图代表已经用掉了多少油。

接下来，我们考虑这个图如何构建：

• 我们用三元组$(i, j, l)$来表示点，意为：第$l$层中的$(i, j)$
• 因为题目中说不消耗钱的话只能向右或者向下，所以： $$(i, j, l) \rightarrow (i, j + 1, l + 1), w = 0$$ $$(i, j, l) \rightarrow (i + 1, j + 1, l), w = 0$$
• 因为题目中说向左或者向上要花钱，所以： $$(i, j, l) \rightarrow (i - 1, j, l + 1), w = b$$ $$(i, j, l) \rightarrow (i, j - 1, l + 1), w = b$$
• 在加油站的时候，情况和上面的就不太一样了，加油站的点应该都要指向该点的第$0$层（因为油必须加满），而且费用为$A$: $$(i, j, l) \rightarrow (i, j, 0), w = A$$
• 还有就是不在加油站时可以随意添加油站，就是要花钱罢了： $$(i, j, l) \rightarrow (i, j, 0), w = A + C$$

在图建立完之后，我们就可以发现：求最小费用其实就是求最短路，然后最后无论剩多少油都是可能的，所以我们要把$(n, n, l)$都遍历一下取一个最小。

还有一点：要注意不要数组越界，这就是为什么代码里有好多if

代码

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

using namespace std;

const int MAXN = 105;
const int MAXK = 15;

int n, k, a, b, c;
int head[MAXN * MAXN * MAXK], dis[MAXN * MAXN * MAXK], ecnt = 2;
bool vis[MAXN * MAXN * MAXK];
struct edge { int to, next, w; } g[2 * 7 * MAXK * MAXN * MAXN];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, head[u], w }; head[u] = ecnt ++; }
void add_edge(int x1, int y1, int l1, int x2, int y2, int l2, int w) {
	add_edge((y1 - 1) * n + x1 + l1 * n * n, (y2 - 1) * n + x2 + l2 * n * n, w);
}

struct node {
	int dis, pos;
	friend bool operator < (const node &a, const node &b) { return a.dis > b.dis; }
};
priority_queue<node> q;

void dijkstra() {
	for (int i = 1; i <= n * n * (k + 1); i ++) dis[i] = ((1 << 30) - 1) * 2;
	dis[1] = 0;
	q.push((node) { dis[1], 1 });
	while (!q.empty()) {
		int u = q.top().pos; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int e = head[u]; e; e = g[e].next) {
			int v = g[e].to;
			if (dis[v] > dis[u] + g[e].w) {
				dis[v] = dis[u] + g[e].w;
				q.push((node) { dis[v], v });
			}
		}
	}
}

int main() {
	cin >> n >> k >> a >> b >> c;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			int oil = 0; cin >> oil;
			if (oil) {
				for (int l = 1; l <= k; l ++)
					add_edge(j, i, l, j, i, 0, a);
				if (i < n) add_edge(j, i, 0, j, i + 1, 1, 0);
				if (j < n) add_edge(j, i, 0, j + 1, i, 1, 0);
				if (i > 1) add_edge(j, i, 0, j, i - 1, 1, b);
				if (j > 1) add_edge(j, i, 0, j - 1, i, 1, b);
			} else {
				for (int l = 0; l < k; l ++) {
					if (i < n) add_edge(j, i, l, j, i + 1, l + 1, 0);
					if (j < n) add_edge(j, i, l, j + 1, i, l + 1, 0);
					if (i > 1) add_edge(j, i, l, j, i - 1, l + 1, b);
					if (j > 1) add_edge(j, i, l, j - 1, i, l + 1, b);
				}
				for (int l = 1; l <= k; l ++)
					add_edge(j, i, l, j, i, 0, c + a);
			}
		}
	}
	dijkstra();
	int ans = ((1 << 30) - 1) * 2;
	for (int l = 0; l <= k; l ++) ans = min(ans, dis[n * n * (1 + l)]);
	cout << ans << endl;
	return 0;
}