Editorial for Đường đi đẹp nhất

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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); } $\]

Editorial for Đường đi đẹp nhất

Comments