#598. MANGGT - Mạng giao thông

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Mạng lưới giao thông thành phố gồm n nút được đánh số từ 1 đến n m đường một chiều nối các cặp nút. Để giảm được độ dài của đường đi ngắn nhất giữa hai nút trọng yếu s t khác nhau, một danh sách gồm k đường hai chiều được đề xuất để xem xét xây dựng.

Nhiệm vụ của bạn là viết một chương trình để chọn ra một đường trong danh sách đề xuất trên để xây dựng sao cho độ dài đường đi ngắn nhất giữa s t (từ s tới t ) là nhỏ nhất.

Dữ liệu vào:

  • Dòng đầu tiên chứa năm số nguyên dương n (n ≤ 10000), m (m ≤ 100000), k (k < 300), s (1 ≤ s ≤ n), t (1 ≤ t ≤ n) cách nhau bởi dấu cách;
  • m dòng tiếp theo, mỗi dòng chứa ba số nguyên dương u, v, c cách nhau bởi dấu cách, trong đó c là độ dài (0 < c ≤ 1000) của đường một chiều từ nút u đến nút v ;
  • k dòng tiếp theo, mỗi dòng chứa ba số nguyên dương x, y q\ (q ≤ 1000) cách nhau bởi dấu trống, trong đó q là độ dài của đường hai chiều được đề xuất để nối giữa hai nút x y .

Dữ liệu ra:

  • Một dòng duy nhất, ghi ra độ dài nhỏ nhất có thể của đường đi ngắn nhất giữa hai nút trọng yếu sau khi xây dựng xong một đường hai chiều từ danh sách đề xuất. Trường hợp không có đường đi từ s đến t , ghi -1 .

Ví dụ:

Dữ liệu vào:
4 5 3 1 4
1 2 13
2 3 19
3 1 25
3 4 17
4 1 18
1 3 23
2 3 5
2 4 25
Dữ liệu ra:
35