Practice · 4 of 5
Lịch thi công — đường tới hạn
CHALLENGE
Difficulty: intermediate+25 XP
**Bài toán.** Dự án có n công đoạn; công đoạn i mất t_i ngày; m ràng buộc "công đoạn u phải XONG trước khi v BẮT ĐẦU". Công đoạn có thể chạy song song nếu không ràng buộc cấm. In số ngày SỚM NHẤT hoàn thành toàn bộ dự án. Đồ thị đảm bảo DAG. **Ràng buộc:** 1 ≤ n ≤ 100 000; 1 ≤ m ≤ 200 000; 1 ≤ t_i ≤ 10^9; 1 ≤ u, v ≤ n. Critical path: fin[v] = max(fin[u]) + t_v theo topo order.
Press Submit to check your solution.
Back to lesson: Practice: Topo Problem Set