Trung tâm kiểm định đồ thị

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

Một hệ thống kiểm định nhận ba mạng độc lập trong cùng một hồ sơ: mạng A cần đếm thành phần liên thông; mạng B cần khoảng cách ngắn nhất không trọng số; mạng C cần chi phí đường đi ngắn nhất có trọng số không âm.

Yêu cầu

Giải ba yêu cầu và in ba đáp án trên ba dòng.

Input

Khối A: n1 m1 và m1 cạnh vô hướng. Khối B: n2 m2 s2 t2 và m2 cạnh vô hướng. Khối C: n3 m3 s3 t3 và m3 cạnh có hướng trọng số không âm.

Output

Dòng 1: số component của A. Dòng 2: khoảng cách BFS của B hoặc -1. Dòng 3: khoảng cách Dijkstra của C hoặc -1.

Ràng buộc

• Mỗi n <= 10^5
• Tổng số cạnh <= 3*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

4 2
1 2
3 4
5 4 1 5
1 2
2 3
3 4
4 5
4 4 1 4
1 2 2
2 4 3
1 3 10
3 4 1

Output

2
4
5

Giải thích. Ba khối có ba dạng graph khác nhau nên lần lượt dùng component-DFS, BFS và Dijkstra.

Ví dụ 2

Input

3 0
3 1 1 3
1 2
3 1 1 3
1 2 5

Output

3
-1
-1

Giải thích. Ba khối có ba dạng graph khác nhau nên lần lượt dùng component-DFS, BFS và Dijkstra.

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

• Yêu cầu bổ sung: nộp Decision Note ngắn, nêu vì sao ba khối cần ba chiến lược khác nhau.

Nguồn: FULLHOUSE DEV – Self-generated.