Cho một DFA đầy đủ. Hãy tìm độ dài của chuỗi ngắn nhất được chấp nhận (bằng BFS trên đồ thị trạng thái). Nếu trạng thái bắt đầu đã là chấp nhận thì kết quả là 0. Nếu ngôn ngữ rỗng, in -1.
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
3 2
1 0
2 0
2 2
0
1 2
Output:
2
Khối mô tả DFA gồm:
n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.s.f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).1 ≤ n ≤ 10^5, 1 ≤ k ≤ 26.
In độ dài chuỗi được chấp nhận ngắn nhất, hoặc -1 nếu không có.
Ví dụ:
Đầu vào:
3 2
1 0
2 0
2 2
0
1 2
Đầu ra:
2
Giải thích:
Đang tải editor...