Hướng dẫn cho Đường đi đẹp nhất
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
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.
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:
Mình xin trình bày lời giải bài này như sau:
Bài này ý tưởng tương tự bài DFS Cơ bản nhưng có hai lưu ý mình xin trình bày ở đây:
Lưu ý 1:
- Bài toán này là đồ thị có hướng.
Lưu ý 2:
- Bài toán này yêu cầu ta cần phải in ra đường đi từ \(s\rightarrow t\) và theo thứ tự từ điển nên ở đây mình sẽ trình bày cách truy vết để ta có thể giải quyết bài toán này
Tiếp theo là phần giải quyết những lưu ý:
- Đối với lưu ý 1: Vì đây là đồ thị có hướng nên lúc đọc đồ thị từ input, ta chỉ sử dụng mỗi lệnh:
\[$
edges[u].push_back(v);
$\]
- Đối với lưu ý 2: Chúng ta sẽ khai báo thêm mảng \(par[]\). Trong đó \(par[u]\) chỉnh là đỉnh cha của đỉnh \(u\). (chú ý rằng: Ở đây, ta có : \(par[s]=s\)).
Mình sẽ đi vào lời giải cụ thể bằng hai cách \(DFS\) như sau:
Cách 1: Không sử dụng cấu trúc dữ liệu stack, mà thay vào đó, chỉ là hàm đệ quy thông thường.
Cách 2: Sử dụng cấu trúc dữ liệu stack
Bước 1:
- Đọc dữ liệu đầu vào tương tự như bài DFS cơ bản, nhưng ở đây ta cần phải sắp xếp theo các đỉnh kề theo tăng dần (đối với cách \(1\)) và giảm dần (đối với cách \(2\))
Bước 2:
- Ta sử dụng một trong hai cách \(DFS\) như hình bên dưới
Bước 3:
- Truy vết để xuất kết quả ra màn hình:
\[$
void solve(ll destination)
{
// dbg(destination);
if (destination == par[destination])
{
res.push_back(destination);
return;
}
res.push_back(destination);
destination = par[destination];
solve(destination);
}
$\]
Như vậy là ta đã giải quyết xong bài toán.
Ps:
Bình luận