#1015. GAMEF - Trò chơi hái hoa

Trong đợt trại hè Tin học miền trung diễn ra tại thành phố ĐNN, ban tổ chức đã tổ chức cho các đoàn trò chơi hái hoa như sau: Có loại hoa (các loại hoa được đánh chỉ số từ đến ) được ban tổ chức sắp xếp tại vị trí (các vị trí được đánh chỉ số từ đến ). Có đoạn đường hai chiều nối giữa các vị trí với nhau đảm bảo luôn có đường đi giữa hai vị trí bất kì, thời gian đi lại trên đoạn đường nối giữa hai vị trí và là . Nhiệm vụ của mỗi đội là xuất phát từ vị trí di chuyển đến đích là vị trí sao cho hái được đủ loại hoa và thời gian về đích là ít nhất. Vì mỗi đội có người chơi nên hoa của mỗi đội là số hoa của cả người gộp lại và thời gian về đích là thời gian lớn nhất của người trong đội. Mỗi người trong đội có thể chọn một hành trình bất kì, có thể đi các đoạn đường giống nhau và mỗi vị trí có thể đến nhiều lần.

Yêu cầu: Xác định thời gian ít nhất của đội giành chiến thắng.

Dữ liệu vào:

• Dòng đầu ghi ba số nguyên
• Trong dòng tiếp theo, dòng thứ ghi thông tin về các loại hoa được bố trí tại ví trí thứ , số đầu tiên ghi số nguyên là số lượng các loại hoa, số tiếp theo là chỉ số các loại hoa ở vị trí đó.
• Trong dòng cuối, mỗi dòng ghi thông tin về một đoạn đường gồm số lần lượt là Các số trên một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

• Ghi ra một số duy nhất là thời gian ít nhất tìm được.

Ví dụ:

Dữ liệu vào:

5 5 5
1 1
1 2
1 3
1 4
1 5
1 2 10
1 3 10
2 4 10
3 5 10
4 5 10

Dữ liệu ra:

30

Giới hạn:

• Có số test tương ứng số điểm có
• Có số test khác tương ứng số điểm có
• Có số test còn lại tương ứng số điểm có