Nội dung Bài tập
- Mã:
- BFS2
- Tên:
- BFS từ S đến T
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- phucnq
Cho đồ thị đơn vô hướng G=(V,U) (không có trọng số), tìm đường đi ngắn nhất từ đỉnh S tới đỉnh T dùng thuật toán tìm kiếm theo chiều rộng.
Input:
Quảng cáo
Input:
- Dòng 1: số đỉnh (nV), số cạnh (nE), đỉnh xuất phát (S), đỉnh kết thúc (T).
- nE dòng tiếp theo mỗi dòng gồm 2 số a, b biểu diễn cạnh ab
In ra đường đi ngắn nhất từ đỉnh S đến đỉnh T. Nếu có nhiều hơn 1 đường đi thì in một đường đi bất kỳ.
Ví dụ:
Input
Output
7 7 1 7
1 2
1 3
2 4
3 4
4 7
5 7
5 6
1 2 4 7
Đồ thị minh họa cho bộ dữ liệu trên:
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <bits/stdc++.h>using namespace std;//Tự cho là gồm 4 chữ số , vì đề bài k n...