算法实现题 汽车加油行驶问题 可以在VC++ 6.0上运行的C++代码,再不行...

发布网友 发布时间：2024-10-22 14:55

我来回答

共1个回答

热心网友 时间：9分钟前

#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;

int dir[4][3] = 
{
-1, 0, 0,
0, -1, 0,
1, 0, 0,
0, 1, 0
};

class point {
public:
int x, y, k, cost;
};

bool operator<(const point& a, const point& b) {
return a.cost > b.cost;
}

int dij(int sx, int sy, int ex, int ey, int size,
int matrix[][100], int K, int A, int B, int C) {
priority_queue<point> q;
int i;
bool vis[100][100][11];
point temp, temp2;
dir[0][2] = dir[1][2] = B;
memset(vis, 0, sizeof(vis));
temp.x = 0;
temp.y = 0;
temp.k = K;
temp.cost = 0;
q.push(temp);
while (!q.empty()) {
temp = q.top();
q.pop();
if (vis[temp.x][temp.y][temp.k]) continue;
vis[temp.x][temp.y][temp.k] = true;
if (temp.x == ex && temp.y == ey) {
return temp.cost;
}
for (i = 0; i < 4; i++) {
temp2.x = temp.x + dir[i][0];
temp2.y = temp.y + dir[i][1];
temp2.cost = temp.cost + dir[i][2];
temp2.k = temp.k - 1;
if (temp2.k < 0) {
continue;
}
if (temp2.x < 0 || temp2.x >= size || temp2.y < 0 || temp2.y >= size) {
continue;
}
if (matrix[temp2.x][temp2.y] == 1) {
temp2.cost += A;
temp2.k = K;
if (!vis[temp2.x][temp2.y][temp2.k])
q.push(temp2);
}
else {
if (!vis[temp2.x][temp2.y][temp2.k])
q.push(temp2);
temp2.cost += A + C;
temp2.k = K;
if (!vis[temp2.x][temp2.y][temp2.k])
q.push(temp2);
}
}
}
return -1;
}

int main() {
ifstream fin("input.txt");
ofstream fout("output.txt");
int N, K, A, B, C, i, j;
int matrix[100][100];
fin >> N >> K >> A >> B >> C;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
fin >> matrix[i][j];
}
}
fout << dij(0, 0, N-1, N-1, N, matrix, K, A, B, C) << endl;
}