### Hiểu về Bài toán
Bài toán "3D path" yêu cầu bạn tìm **đường đi ngắn nhất** từ một ô xuất phát `(1, 1, 1)` đến một ô kết thúc `(n, n, n)` trong một lưới 3D. "Độ dài" của đường đi không phải là số bước, mà là **tổng chi phí** của các ô bạn đi qua. Việc di chuyển giữa các ô chỉ giới hạn ở các ô kề nhau (lên, xuống, trái, phải, tiến, lùi).
Đây là một ví dụ kinh điển về bài toán **đường đi ngắn nhất từ một điểm nguồn** trên một đồ thị có trọng số.
***
### Thuật toán: Dijkstra
Thuật toán tốt nhất cho loại bài toán này, khi trọng số của các cạnh (chi phí của các ô) là không âm, là **thuật toán Dijkstra**.
1. **Biểu diễn Lưới dưới dạng Đồ thị**: Hãy xem mỗi ô `(x, y, z)` trong lưới 3D là một **đỉnh** trong đồ thị. Một cạnh tồn tại giữa hai đỉnh bất kỳ kề nhau. **Trọng số** của một cạnh là chi phí để di chuyển đến ô đích, chính là giá trị `A[x][y][z]` của ô đó.
2. **Sử dụng Hàng đợi ưu tiên (Priority Queue)**: Thuật toán Dijkstra hoạt động bằng cách luôn luôn khám phá đường đi hứa hẹn nhất trước. Để làm điều này một cách hiệu quả, nó sử dụng một **hàng đợi ưu tiên**. Cấu trúc dữ liệu này tự động theo dõi các đỉnh bạn có thể đến, ưu tiên đỉnh có tổng chi phí thấp nhất cho đến hiện tại.
3. **Quy trình Thực hiện**:
* Bắt đầu tại đỉnh nguồn `(1, 1, 1)` với chi phí ban đầu là `0`.
* Lặp đi lặp lại việc trích xuất đỉnh có chi phí nhỏ nhất từ hàng đợi ưu tiên.
* Với mỗi đỉnh được trích xuất, hãy xem xét các đỉnh lân cận của nó.
* Nếu bạn tìm thấy một đường đi mới đến một đỉnh lân cận ngắn hơn bất kỳ đường đi nào đã tìm thấy trước đó, hãy cập nhật chi phí của đỉnh lân cận đó và thêm nó vào hàng đợi ưu tiên.
4. **Tìm Đáp án**: Thuật toán tiếp tục cho đến khi nó đạt đến đỉnh đích `(n, n, n)`. Chi phí cuối cùng được lưu trữ cho đỉnh đích chính là đáp án của bạn.
***
### Tại sao Thuật toán này Hoạt động
Thuật toán Dijkstra đảm bảo tìm thấy đường đi ngắn nhất nhờ vào bản chất tham lam của nó. Bằng cách luôn chọn mở rộng từ đỉnh có chi phí hiện tại thấp nhất, bạn đảm bảo rằng mình tìm thấy đường đi ngắn nhất đến mọi đỉnh có thể đến được. Vì tất cả chi phí của các ô đều là số dương, bạn sẽ không bao giờ tìm thấy một đường tắt có chi phí âm làm mất hiệu lực các lựa chọn trước đó của mình.
### Accepted code
<details><summary>CLICK ME</summary>
<p>
```
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
using namespace std;
const long long INF = 1e18;
// Struct to store state in the priority queue: (cost, x, y, z)
// A custom comparator is defined to create a min-heap
struct State {
long long cost;
int x, y, z;
bool operator>(const State& other) const {
return cost > other.cost;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
// Use a 3D vector to store the grid values. Using 0-based indexing.
vector<vector<vector<int>>> A(n, vector<vector<int>>(n, vector<int>(n)));
// Read the 3D grid input according to the specified format
for (int i = 0; i < n * n; ++i) {
int x = (i / n);
int y = (i % n);
for (int z = 0; z < n; ++z) {
cin >> A[x][y][z];
}
}
// Distance grid to store the shortest cost to each cell
vector<vector<vector<long long>>> dist(n, vector<vector<long long>>(n, vector<long long>(n, INF)));
// Min-heap priority queue
priority_queue<State, vector<State>, greater<State>> pq;
// The cost of the starting cell (1, 1, 1) is not included, so its initial distance is 0.
dist[0][0][0] = 0;
pq.push({0, 0, 0, 0});
int dx[] = {1, -1, 0, 0, 0, 0};
int dy[] = {0, 0, 1, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};
while (!pq.empty()) {
State current = pq.top();
pq.pop();
long long current_cost = current.cost;
int x = current.x;
int y = current.y;
int z = current.z;
// Skip if a shorter path has already been found
if (current_cost > dist[x][y][z]) {
continue;
}
// Break if the destination is reached
if (x == n - 1 && y == n - 1 && z == n - 1) {
break;
}
// Explore 6 neighbors
for (int i = 0; i < 6; ++i) {
int new_x = x + dx[i];
int new_y = y + dy[i];
int new_z = z + dz[i];
// Check for valid coordinates
if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < n && new_z >= 0 && new_z < n) {
int move_cost = A[new_x][new_y][new_z];
long long new_total_cost = current_cost + move_cost;
if (new_total_cost < dist[new_x][new_y][new_z]) {
dist[new_x][new_y][new_z] = new_total_cost;
pq.push({new_total_cost, new_x, new_y, new_z});
}
}
}
}
cout << dist[n-1][n-1][n-1] << endl;
return 0;
}
```
</p>
</details>
djoker
Created at
1 likes