洛谷P4009汽车加油行驶问题解析

### 问题背景
该问题是网络流24题之一，虽然标签可能有些误导，但实际上可以通过最短路径算法来解决。

### 问题分析
在仔细阅读题目后，我们可以发现这实际上是一个最短路径问题。不过，由于涉及到加油的限制，我们需要使用一个三维数组 `dis[x][y][res]` 来记录当前在位置 `(x, y)` 时，剩余油量为 `res` 的最小花费。

### 算法思路
我们从起点 `(1, 1)` 开始，目标是到达终点 `(n, n)`。每次扩展节点时，需要考虑加油的花费。如果当前位置有油库，则必须加油；否则可以选择是否加油。

### 代码实现
```cpp
#include
#include
using namespace std;

typedef tuple pit; // x, y, res
constexpr int fx[5][2] = {{0, 0}, {1, 0}, {0, -1}, {-1, 0}, {0, 1}};
int n, K, A, B, C, ans = numeric_limits::max();
int dis[150][150][20];
bool in[150][150][20], oil[150][150];

struct cmp {
bool operator()(pit a, pit b) {
return dis[get<0>(a)][get<1>(a)][get<2>(a)] > dis[get<0>(b)][get<1>(b)][get<2>(b)];
}
};

__gnu_pbds::priority_queue q;

void SPFA();

int main() {
scanf("%d%d%d%d%d", &n, &K, &A, &B, &C);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int col;
scanf("%d", &col);
oil[i][j] = (col == 1);
}
}
SPFA();
for (int i = 0; i <= K; i++) {
ans = min(ans, dis[n][n][i]);
}
printf("%d", ans);
}

void SPFA() {
memset(dis, 0x7f, sizeof(dis));
dis[1][1][K] = 0;
in[1][1][K] = true;
q.push(make_tuple(1, 1, K));
while (!q.empty()) {
int x, y, res;
tie(x, y, res) = q.top();
q.pop();
in[x][y][res] = false;
if (oil[x][y] && res != K) {
if (dis[x][y][K] > dis[x][y][res] + A) {
dis[x][y][K] = dis[x][y][res] + A;
if (!in[x][y][K]) {
q.push(make_tuple(x, y, K));
in[x][y][K] = true;
}
}
continue;
}
if (dis[x][y][K] > dis[x][y][res] + A + C) {
dis[x][y][K] = dis[x][y][res] + A + C;
if (!in[x][y][K]) {
q.push(make_tuple(x, y, K));
in[x][y][K] = true;
}
}
if (res <= 0) continue;
for (int i = 1; i <= 4; i++) {
int xi = x + fx[i][0], yi = y + fx[i][1];
if (xi <1 || xi > n || yi <1 || yi > n) continue;
int cost = (xi if (dis[xi][yi][res - 1] > dis[x][y][res] + cost) {
dis[xi][yi][res - 1] = dis[x][y][res] + cost;
if (!in[xi][yi][res - 1]) {
q.push(make_tuple(xi, yi, res - 1));
in[xi][yi][res - 1] = true;
}
}
}
}
}
```

### 注意事项
代码中使用了 `__gnu_pbds::priority_queue` 和 `std::tuple`，这些高级数据结构可能会对某些编译器不友好，请根据实际情况进行调整。

### 总结
通过上述分析和代码实现，我们可以有效地解决汽车加油行驶问题。希望本文能对大家理解和解决类似问题有所帮助。