G2W - Đi làm
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Bài 2 của đề /ckfinder/userfiles/files/TEST2.pdf

Tom sống ở thành phố XYZ, hàng ngày anh thường chọn đường đi ngắn nhất từ nhà tới cơ quan và từ cơ quan về nhà. Thành phố XYZ mà Tom ở có 𝑛 nút giao thông được đánh số từ 1 đến 𝑛. Nhà Tom nằm ở nút giao thông 1 còn cơ quan nằm ở nút giao thông 𝑛. Từ nút giao thông 𝑖 đến nút 𝑗 có không quá một đường đi một chiều độ dài 𝑑𝑖𝑗 , tất nhiên, có thể có đường đi một chiều khác đi từ nút 𝑗 đến nút 𝑖. Trong thời gian tới, thành phố sẽ tổ chức nhiều sự kiện văn hóa và Tom biết rằng, khi đi làm từ nhà đến cơ quan thì có 𝑝 nút sẽ bị ùn tắc là 𝑎1, 𝑎2, . . , 𝑎𝑝, còn khi đi từ cơ quan về nhà thì có 𝑞 nút sẽ bị ùn tắc là 𝑏1, 𝑏2, . . , 𝑏𝑞. Tom băn khoăn muốn biết độ dài đường ngắn nhất đi từ nhà đến cơ quan mà không đi qua các nút 𝑎1, 𝑎2, . . , 𝑎𝑝 và độ dài đường ngắn nhất đi từ cơ quan về nhà mà không đi qua các nút 𝑏1, 𝑏2, . . , 𝑏𝑞 là bao nhiêu?

Ví dụ, thành phố có 5 nút giao thông và các đường đi một chiều với độ dài tương ứng như hình bên. Giả sử nút 4 là nút bị ùn tắc khi đi từ nhà đến cơ quan, nút 2 và nút 4 là nút bị ùn tắc khi đi từ cơ quan về nhà, khi đó độ dài đường đi ngắn nhất từ nhà đến cơ quan là 19 (đường đi 1→2→3→5, không đi qua nút 4), độ dài đường đi ngắn nhất từ cơ quan về nhà là 17 (đường đi 5→3→1, không đi qua nút 2 và nút 4)

Yêu cầu: Cho biết các đường đi một chiều với độ dài tương ứng mô tả hệ thống giao thông thành phố XYZ và các nút sẽ bị ùn tắc 𝑎1, 𝑎2, . . , 𝑎𝑝, 𝑏1, 𝑏2, . . , 𝑏𝑞. Hãy tìm độ dài đường đường đi ngắn nhất để đi từ nhà (nút giao thông 1) đến cơ quan (nút giao thông 𝑛) mà không đi qua các nút 𝑎1, 𝑎2, . . , 𝑎𝑝 và từ cơ quan về nhà mà không qua các nút 𝑏1, 𝑏2, . . , 𝑏𝑞.

Dữ liệu vào

- Dòng đầu ghi bốn số nguyên dương 𝑛, 𝑚, 𝑝, 𝑞 (3 ≤ 𝑛 ≤ 10000, 𝑚 ≤ 105 , 1 ≤ 𝑝, 𝑞 ≤ 𝑛 − 2)
- Dòng thứ hai ghi 𝑝 số nguyên 𝑎1, 𝑎2, . . , 𝑎𝑝 (1 < 𝑎𝑖 < 𝑛)
- Dòng thứ ba ghi 𝑞 số nguyên 𝑏1, 𝑏2, . . , 𝑏𝑞 (1 < 𝑏𝑖 < 𝑛)
- 𝑚 dòng tiếp theo, mỗi dòng 3 số nguyên 𝑖,𝑗, 𝑑𝑖𝑗 (1 ≤ 𝑖,𝑗 ≤ 𝑛, 0 < 𝑑𝑖𝑗 ≤ 30000) mô tả có đường đi một chiều từ 𝑖 đến 𝑗 có độ dài 𝑑𝑖𝑗. Hai số liên tiếp trên một dòng cách nhau một dấu cách. Dữ liệu bảo đảm luôn có nghiệm.

Kết quả

Một dòng chứa 2 số nguyên cách nhau một dấu cách, số thứ nhất là độ dài đường đi ngắn nhất từ nhà đến cơ quan, số thứ hai là độ dài ngắn nhất từ cơ quan về nhà thỏa mãn điều kiện đã nêu.

Ví dụ

Input

5 11 1 2
4
2 4
1 2 10
1 4 3
2 3 6
2 5 10
3 1 12
3 4 6
3 5 3
4 1 5
4 3 5
5 3 5
5 4 10

Output

19 17

Giới hạn:

50% số test ứng với 50% số điểm  n<=100.


Nguồn: 3D '1819

Back to Top