Bộ chọn chiến lược đồ thị

Bối cảnh và bài toán

Trước khi lập trình, nhóm kỹ thuật phải chọn thuật toán phù hợp từ mô tả workload. Mỗi tình huống thuộc đúng một trong sáu nhóm đã học.

Yêu cầu

Với mỗi tình huống, in tên chiến lược thích hợp nhất: DFS, BFS, TOPO, DIJKSTRA, BELLMAN_FORD hoặc FLOYD.

Input

Dòng đầu T. Mỗi tình huống gồm 5 số: directed, weighted, hasNegative, allPairs, needOrder. Quy ước: nếu needOrder=1 là DAG ordering; nếu allPairs=1 ưu tiên all-pairs; nếu weighted=0 là đồ thị không trọng số.

Output

In một nhãn thuật toán cho mỗi tình huống.

Ràng buộc

• 1 <= T <= 10^5 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

5
0 0 0 0 0
1 0 0 0 1
1 1 0 0 0
1 1 1 0 0
0 1 0 1 0

Output

BFS
TOPO
DIJKSTRA
BELLMAN_FORD
FLOYD

Giải thích. Các cờ mô tả trực tiếp loại workload; áp dụng Decision Map cho từng tình huống.

Ví dụ 2

Input

2
1 0 0 0 0
0 0 0 0 0

Output

DFS
BFS

Giải thích. Các cờ mô tả trực tiếp loại workload; áp dụng Decision Map cho từng tình huống.

Gợi ý

Hãy bắt đầu bằng cách phân loại graph, mục tiêu truy vấn và constraints; sau đó đối chiếu với Decision Map của buổi học trước khi viết code.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.