Bài 2:
Ý em hoàn toàn giống như anh myhanh (nhưng minpath từ s đến t chỉ BFS thôi
). Nhưng cách này có thể die 1 số test vì chương trình chạy chậm.
Có 1 cách nhanh hơn là dựa trên nhận xét:
_Giả sử các đỉnh trên đường đi ngắn nhất lần lượt là s(1),s(2),...,s(k)
_Rõ ràng nếu từ s(1) ta có thể đi đến s(i) nào đó thì các đỉnh từ s(2) đến s(i-1) chắc chắn ko phải nút xung yếu (vì tồn tại đường đi s(1),s(i),s(i+1),...,s(k))