汽车加油 / 汽车加油行驶问题

题目链接：ybt高效进阶3-3-4 / luogu P4009

题目大意

你要从一个网格的左上角点走到右下角点。
可以想四个方向行动，然后自己可以独立走 K 步，走到油站就重新算，但是有花费 A。可以自己建油站，费用为 C。
如果你要走向 x 或 y 坐标减少的地方，还要花费 B。
问你最小花费。

思路

看到数据范围，发现很小，我们考虑把点拆开。
我们让原来的一个点拆开，原来只是记录在哪个位置，现在我们把拆开的点还多一个值，就是还能走多少步数（在不去油站的情况下）

那我们考虑怎么转移。
那首先，我们可以在这个地方弄油站（要么就现成，要么就自己弄）。第二，我们可以网四个方向走，而且如果是往上或往左，要记得费用加 $B$。
然后啊，还有一点就是，如果这个地方原来就是有油站的，那你就会被强迫消费，那你剩余行走次数就只能从 $K$ 开始转移。

然后你会发现它可以直接用最短路来做，我这里用的是 SPFA。
你就把每个状态都弄一个编号，然后转移所加上的值就是连边的边的权值。边连着的点就是从哪个状态转移到哪个状态。

听说还可以用网络流来搞。
以后再说吧。

代码

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

using namespace std;

struct node {
	int x, to, nxt;
}e[2000001];
int n, K, le[1000001], KK;
long long a, b, c, dis[1000001], ans;
int pl[101][101];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int b_c[4] = {0, 0, 1, 1};
bool in[1000001];
queue <int> q;

int get_num(int x, int y, int oil) {
	return oil * (n * n) + (x - 1) * n + y - 1 + 1;
}

void add(int x, int y, int z) {
	e[++KK] = (node){z, y, le[x]}; le[x] = KK;
}

bool check(int x, int y) {
	if (x < 1 || x > n) return 0;
	if (y < 1 || y > n) return 0;
	return 1;
}

void spfa() {//SPFA跑最短路
	memset(dis, 0x7f, sizeof(dis));
	
	in[get_num(1, 1, K)] = 1;
	dis[get_num(1, 1, K)] = 0;
	q.push(get_num(1, 1, K));
	
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
		for (int i = le[now]; i; i = e[i].nxt)
			if (dis[e[i].to] > dis[now] + e[i].x) {
				dis[e[i].to] = dis[now] + e[i].x;
				if (!in[e[i].to]) {
					in[e[i].to] = 1;
					q.push(e[i].to);
				}
			}
		
		in[now] = 0;
	}
}

int main() {
	scanf("%d %d %lld %lld %lld", &n, &K, &a, &b, &c);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &pl[i][j]);
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k < K; k++)//加油
				if (pl[i][j]) add(get_num(i, j, k), get_num(i, j, K), a);
					else add(get_num(i, j, k), get_num(i, j, K), a + c);
			
			for (int k = 0; k < 4; k++)//走
				if (check(i + dx[k], j + dy[k])) {
					if (!pl[i][j]) {
						for (int l = 1; l <= K; l++) {
							if (b_c[k])	add(get_num(i, j, l), get_num(i + dx[k], j + dy[k], l - 1), b);
								else add(get_num(i, j, l), get_num(i + dx[k], j + dy[k], l - 1), 0);
						}
					}
					else {//强制消费
						if (b_c[k]) add(get_num(i, j, K), get_num(i + dx[k], j + dy[k], K - 1), b);
							else add(get_num(i, j, K), get_num(i + dx[k], j + dy[k], K - 1), 0);
					}
				}
		}
	
	spfa();
	
	ans = dis[0];
	for (int i = 0; i <= K; i++)
		ans = min(ans, dis[get_num(n, n, i)]);//统计,到终点的时候剩下步数没有规定，都可以，要枚举找最小值
	
	printf("%lld", ans);
	
	return 0;
}