FUKU11J - Round Trip
Giới hạn- Thời gian: 0.1s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Jim đang chuẩn bị đi thăm một trong số những người bạn tốt nhất của cậu ấy ở trong thành phố trên núi cao. Đầu tiên, cậu ấy rời khỏi thành phố của mình và đi đến thành phố đích, gọi là lượt đi. Sau đó cậu ấy lại quay trở về thành phố của mình, gọi là lượt về. Bạn được yêu cầu viết một chương trình tính chi phí nhỏ nhất cho chuyến hành trình này, được tính bằng tổng chi phí của lượt đi và lượt về.
Có một mạng lưới đường đi giữa những thành phố này. Mọi con đường đều là một chiều. Mỗi đường cần một chi phí nhất định để di chuyển qua nó.
Ngoài chi phí phải trả cho các con đường, còn phải trả một khoản phí cho mỗi thành phố trên đường đi. Tuy nhiên, vì đây là phí visa cho thành phố, nên ta chỉ phải trả 1 lần duy nhất khi lần đầu tiên tới 1 thành phố nào đó.
Độ cao của mỗi thành phố được cho trước. Trong lượt đi, không được phép sử dụng các con đường đi xuống (tức là nếu đi từ a đến b thì độ cao của a không được lớn hơn độ cao của b). Trong lượt về thì không được sử dụng các đường đi lên. Nếu độ cao của a và b bằng nhau thì nó có thể được sử dụng ở cả lượt đi lẫn lượt về.
Input
Dữ liệu vào chứa một số bộ test theo định dạng như sau:
n m
d
2
e
2
d
3
e
3
.
.
.
d
n-1
e
n-1
a
1
b
1
c
1
a
2
b
2
c
2
.
.
.
a
m
b
m
c
m
Mỗi giá trị đều là số nguyên không âm và được ngăn cách nhau bằng dấu cách.
n là số lượng thành phố trong mạng, m là số lượng đường 1 chiều. Dữ liệu đảm bảo 2 ≤ n ≤ 50 và 0 ≤ m ≤ n ( n −1). Các thành phố được đánh số từ 1 đến n . Thành phố 1 là thành phố khởi hành của Jim, và thành phố n là đích đến.
d i là phí visa của thành phố i , và e i là độ cao của nó. Đảm bảo 1 ≤ d i ≤ 1000 và 1≤ e i ≤ 999 với 2≤ i ≤ n −1. Thành phố 1 và n không yêu cầu phí visa. Độ cao của thành phố 1 là 0, và độ cao của thành phố n là 1000. Các thành phố khác nhau có thể có cùng độ cao, nhưng có không quá 10 thành phố với cùng 1 độ cao.
Con đường thứ j là từ thành phố a j đến thành phố b j với chi phí c j (1 ≤ j ≤ m ). Với 1 ≤ a j ≤ n , 1 ≤ b j ≤ n , và 1 ≤ c j ≤ 1000. Bạn có thể đi trực tiếp từ a j đến b j , nhưng không thể đi từ b j đến a j trừ khi có một con đường khác từ b j đến a j được cho trong bộ test. Không có 2 con đường cùng nối 1 cặp thành phố theo cùng 1 chiều, tức là, với mọi i và j mà i ≠ j , thì a i ≠ a j hoặc b i ≠ b j . Không có con đường nào nối 1 thành phố với chính nó, nghĩa là với mọi j , thì a j ≠ b j .
Cuối cùng là 1 dòng chứa 2 số 0 đánh dấu kết thúc dữ liệu.
Output
Với mỗi bộ test, in ra 1 dòng chứa chi phí nhỏ nhất (kể cả phí visa) của hành trình tìm được. Nếu không tồn tại hành trình nào thoả mãn thì in ra “-1”.
Example
Input:
3 6
3 1
1 2 1
2 3 1
3 2 1
2 1 1
1 3 4
3 1 4
3 6
5 1
1 2 1
2 3 1
3 2 1
2 1 1
1 3 4
3 1 4
4 5
3 1
3 1
1 2 5
2 3 5
3 4 5
4 2 5
3 1 5
2 1
2 1 1
0 0
Output:
7
8
36
-1
- Người up: racer
- Nguồn bài: ACM ICPC Fukuoka 2011