Mỗi dịch vụ cần một thời lượng để khởi động. Các dịch vụ độc lập chạy song song, nhưng một dịch vụ chỉ bắt đầu sau khi tất cả dịch vụ nó phụ thuộc đã khởi động xong.
Thời gian hoàn tất của một dịch vụ = (thời điểm muộn nhất các phụ thuộc xong) + thời lượng của nó. Tổng thời gian khởi động hệ thống = thời điểm dịch vụ cuối cùng hoàn tất (chính là đường găng / longest path).
Quan hệ A B nghĩa là A khởi động trước B (B phụ thuộc A).
net(5)→db(3): db xong tại 5+3=8 → hệ thống mất 8.
Dòng đầu là n. n dòng tiếp theo, mỗi dòng gồm tên dịch vụ và thời lượng (số nguyên). Dòng tiếp là m, sau đó m dòng A B (A trước B).
1 ≤ n ≤ 100. 1 ≤ thời lượng ≤ 1000. Đồ thị không có chu trình.
Một số nguyên: tổng thời gian khởi động hệ thống.
Ví dụ:
Đầu vào:
2
net 5
db 3
1
net db
Đầu ra:
8
Giải thích:
Đang tải editor...