cpp-060Đọc toàn bộ đề miễn phí
DP trên DAG: Đường đi Dài nhất và Đếm số Đường đi
Cho một đồ thị có hướng không có chu trình (DAG) gồm N đỉnh và M cạnh. Đỉnh xuất phát là 1 và đỉnh kết thúc là N. Hãy tính:
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: stl, pointers, trees and graphs.
Nội dung đề bài
Mô tả bài toán
Mô tả bài toán
Cho một đồ thị có hướng không có chu trình (DAG) gồm N đỉnh và M cạnh. Đỉnh xuất phát là 1 và đỉnh kết thúc là N. Hãy tính:
- Độ dài đường đi dài nhất từ 1 đến N (tính theo số cạnh). Nếu không có đường đi từ 1 đến N, in ra -1.
- Số lượng đường đi khác nhau từ 1 đến N modulo 109 + 7.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng đầu tiên gồm 2 số nguyên N, M (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000).
- M dòng tiếp theo, mỗi dòng gồm 2 số nguyên u, v mô tả cạnh có hướng từ u đến v (1 ≤ u, v ≤ N).
Output
- In ra hai số nguyên cách nhau bởi dấu cách: độ dài đường đi dài nhất và số lượng đường đi modulo 109 + 7. Nếu không tới được N, in ra
-1 0.
Ràng buộc
- Thời gian: 1.0s. Bộ nhớ: 256MB.
Ví dụ 1
Input
4 5
1 2
1 3
2 4
3 4
2 3Output
3 3Giải thích
Dữ liệu đầu vào mẫu và kết quả tương ứng theo đúng đặc tả giải thuật.
Ví dụ 2
Input
3 1
1 2Output
-1 0Giải thích
Dữ liệu kiểm thử trường hợp biên và kết quả trả về tương ứng.
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.