Hệ thống giao thông thành phố nơi hai bạn Bình và An sống có n nút giao thông được đánh số từ 1 đến n và m con đường một chiều trong đó con đường thứ i nối nút
Yêu cầu: Bạn cần tìm giải pháp cho k ngày (các ngày được đánh số từ 1 đến k). Với ngày thứ i tổng thời gian di chuyển ít nhất của Bình và An là bao nhiêu giây? Biết rằng, ngày thứ i (i = 1..k) Bình di chuyển mỗi km mất
Dữ liệu vào:
- Dòng đầu tiên ghi 3 số nguyên n,m,k (2 ≤ n ≤
;1 ≤ m ≤2. ;1 ≤ k ≤ 100). - Dòng thứ i (i=1…m) trong m dòng tiếp theo, mỗi dòng ghi 3 số nguyên
, , (1≤ , ≤n;1≤ ≤ ). - Dòng thứ j (j=1…k) trong k dòng tiếp theo, mỗi dòng số nguyên
, (1≤ , ≤ ).
Kết quả:
Gồm k dòng, dòng thứ i(i=1…k) cho biết tổng thời gian ít nhất mà hai bạn di chuyển trong ngày thứ i.
Ví dụ:
INPUT
4 4 2
1 2 2
1 3 9
4 2 8
4 3 3
7 3
3 6
OUTPUT
38
45
Giới hạn:
Có 30% số test tương ứng 30% số điểm có 2≤n≤100.
Có 30% số test khác tương ứng 30% số điểm có n≤1000.
Có 40% số test khác tương ứng 40% số điểm có: n≤
Comments