Hướng dẫn cho Đường đi (Contest Practice VNOI 2021 Round 6)
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask 1: \(n,q \le 500\)
Với mỗi truy vấn, ta Dijkstra từ \((x,y)\). Độ phức tạp: \(O(qmnlog_2(mn))\)
Subtask 2: \(m = 2\)
Không mất tổng quát, giả sử \(y < v\). Đặt dp[i][j] là khoảng cách ngắn nhất khi đi từ \((x,y)\) tới \((i,j)\). Việc tính dp[i][j] chỉ phụ thuộc vào dp[..][j-1] nên với mỗi truy vấn sẽ tốn \(O(n)\).
ĐPT \(O(q.n)\)
Subtask 3: \(n \le 500\)
Gom những truy vấn có chung vị trí xuất phát \((x,y)\) lại với nhau để xử lý. Nhận thấy chỉ có tối đa \(m \times n\) nhóm như vậy nên chỉ cần Dijkstra \(O(mn)\) lần.
ĐPT \(O(m^2n^2log_2(mn))\)
Subtask 4:
Ta có tính chất: Giả sử đường đi tối ưu từ \((x,y)\) tới \((u,v)\) phải đi qua cột \(t\) thì tồn tại một ô \((z,t)\) nằm trên đường đi ấy.
Dùng thuật toán chia để trị để giải quyết.
Xét đoạn mã giả sau:
void solve(tập truy vấn S, biên trái L, biên phải R) {
if (L > R hoặc S rỗng) return
int mid = random(L,R)
for (int row = 1; row <= m; row++) {
dijkstra((row,mid), L,R)
//dijkstra từ ô trên cột mid, chỉ đi trong phạm vi từ cột L tới cột R
Cập nhật đáp án cho mọi truy vấn trong tập S (giả sử như đường đi có chứa ô (row,mid))
}
Tập con trái = {q thuộc S | truy vấn q có max(y,v) < mid}
Tập con phải = {q thuộc S | truy vấn q có min(y,v) > mid}
solve(Tập con trái, L,mid-1)
solve(Tập con phải, mid+1,R)
}
Một điểm đáng chú ý là hàm bên trên chỉ Dijkstra trong phạm vi \([L,R]\) chứ không phải toàn bộ bảng. Làm vậy vẫn xét hết được mọi trường hợp là do: khi gọi solve(L,R) thì trường hợp đường đi tối ưu ra ngoài phạm vi \([L,R]\) đã được giải quyết. Thật vậy, ở lần gọi đầu tiên solve(1,n), không có đường đi nào ra ngoài bảng. Trong hàm solve(), khi gọi đệ quy xuống tập con trái, mọi đường đi ra khỏi phạm vi \([L,mid-1]\) (nhưng vẫn thuộc \([L,R]\)) thì buộc phải đi qua một ô trên cột mid, vì vậy trường hợp này đã được xét. Tương tự cho tập con phải.
Điều này làm giảm thời gian đi khá đáng kể.
Độ phức tạp của mỗi hàm solve() là:
\(O(m \times m(R-L+1)log_2(m(R-L+1)) + m \times |S|)\)
(Dijkstra và duyệt tập S tới \(m\) lần)
Nếu chọn mid = (L+R) / 2 - điểm chính giữa thì tổng \(|S|\) trong mọi hàm solve là \(O(qlog_2(n))\), tổng kích thước bảng cần phải Dijkstra là \(O(m \times mnlog2(n))\) (thử hình dung cây nhị phân/ thuật toán quick sort)
Độ phức tạp \(O(qlog_2(n)+m^2nlog_2(n)log_2(mn))\)
Source code:
// Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_M = 8;
const int MAX_N = 5005;
const int MAX_Q = 300005;
const int DIRECT_X[4] = {0, 1, 0, -1};
const int DIRECT_Y[4] = {-1, 0, 1, 0};
struct Query
{
int x, y, u, v;
};
int n, m, numQuery;
int arr[MAX_M][MAX_N];
Query queries[MAX_Q];
int answer[MAX_Q];
int dist[MAX_M][MAX_N];
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
void dijkstra(int x, int y, int left, int right)
{
for (int row = 1; row <= m; row++)
{
memset(dist[row] + left, 0x3f, sizeof(int) * (right - left + 1));
}
dist[x][y] = arr[x][y];
pq.push(make_tuple(dist[x][y], x, y));
while (!pq.empty())
{
int cost;
tie(cost, x, y) = pq.top();
pq.pop();
if (cost != dist[x][y])
{
continue;
}
for (int i = 0; i < 4; i++)
{
int u = x + DIRECT_X[i], v = y + DIRECT_Y[i];
if (1 <= u && u <= m && left <= v && v <= right && dist[u][v] > cost + arr[u][v])
{
dist[u][v] = cost + arr[u][v];
pq.push(make_tuple(dist[u][v], u, v));
}
}
}
}
void solve(vector<int> queryIds, int left, int right)
{
if (left > right || queryIds.empty())
{
return;
}
int mid = (left + right) / 2;
for (int row = 1; row <= m; row++)
{
dijkstra(row, mid, left, right);
for (auto &id : queryIds)
{
answer[id] = min(answer[id], dist[queries[id].x][queries[id].y] + dist[queries[id].u][queries[id].v] - arr[row][mid]);
}
}
vector<int> leftQueryIds, rightQueryIds;
for (auto &id : queryIds)
{
if (max(queries[id].y, queries[id].v) < mid)
{
leftQueryIds.push_back(id);
}
if (min(queries[id].y, queries[id].v) > mid)
{
rightQueryIds.push_back(id);
}
}
solve(leftQueryIds, left, mid - 1);
solve(rightQueryIds, mid + 1, right);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef Flower_On_Stone
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
cin >> m >> n;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> arr[i][j];
}
}
cin >> numQuery;
vector<int> queryIds;
for (int i = 1; i <= numQuery; i++)
{
cin >> queries[i].x >> queries[i].y >> queries[i].u >> queries[i].v;
queryIds.push_back(i);
}
memset(answer, 0x3f, sizeof(int) * (numQuery + 1));
solve(queryIds, 1, n);
for (int i = 1; i <= numQuery; i++)
{
cout << answer[i] << '\n';
}
return 0;
}
Bình luận