Mô tả và yêu cầu

Đường đi
Cho đa đồ thị vô hướng trọng số 𝐺 = (𝑉, 𝐸), đặt 𝑛 = |𝑉|, 𝑚 = |𝐸|. Các đỉnh được đánh số từ 1
đến 𝑛. Người ta định nghĩa trọng số của một đường đi từ đỉnh 𝑢 đến đỉnh 𝑣 là trọng số lớn nhất
trong các trọng số trên cạnh của đường đi. Trong các đường đi từ 𝑢 đến 𝑣, chúng ta chỉ quan tâm
đến các đường đi có trọng số nhỏ nhất và bằng đúng 𝑊.
Yêu cầu: Cho đồ thị 𝐺, cho 𝑊 và hai tập 𝐴, 𝐵(𝐴∩ 𝐵 = ∅; 𝐴,𝐵 ⊂ 𝑉), đếm số cặp đỉnh 𝑢, 𝑣 với
𝑢 ∈ 𝐴,𝑣 ∈ 𝐵 mà đường đi có trọng số nhỏ nhất từ 𝑢 đến 𝑣 bằng đúng 𝑊.
Dữ liệu: Vào từ file văn bản PATH.INP:
- Dòng đầu chứa năm số nguyên dương 𝑛, 𝑚, 𝑊, 𝑛𝐴, 𝑛𝐵 (𝑊 ≤ 109);
- Tiếp theo là 𝑚 dòng mô tả các cạnh của đồ thị, mỗi dòng chứa 3 số nguyên dương
𝑖,𝑗,𝑐𝑖𝑗 (𝑐𝑖𝑗 ≤ 109);
- Tiếp theo là một dòng chứa 𝑛𝐴 số nguyên dương 𝑢1, 𝑢2, … ,𝑢𝑛𝐴 mô tả tập 𝐴;
- Tiếp theo là một dòng chứa 𝑛𝐵 số nguyên dương 𝑣1, 𝑣2, … ,𝑣𝑛𝐵 mô tả tập 𝐵.
Kết quả: Ghi ra file văn bản PATH.OUT gồm một dòng là số cặp đỉnh 𝑢, 𝑣 mà 𝑢 ∈ 𝐴,𝑣 ∈ 𝐵 mà
đường đi có trọng số nhỏ nhất từ 𝑢 đến 𝑣 bằng đúng 𝑊.

Giới hạn và chấm điểm

 Có 40% số lượng test ứng với 40% số điểm của bài thỏa mãn điều kiện: 𝑛𝐴 = 𝑛𝐵 = 1; 𝑛 ≤
103; 𝑚 ≤ 105;

 Có 30% số lượng test khác ứng với 30% số điểm của bài thỏa mãn điều kiện: 𝑛𝐴, 𝑛𝐵 ≤ 102;
𝑛 ≤ 105; 𝑚 ≤ 3 × 105;

 Có 30% số lượng test còn lại ứng với 30% số điểm của bài thỏa mãn điều kiện: 𝑛 ≤ 105; 𝑚 ≤
3 × 105;

Ví dụ

PATH.INP                      PATH.OUT                                   Hình minh họa
 4 6 2 1 2                     1
 1 2 1
 1 3 1
 1 4 2
 2 3 2
 3 4 2
 2 4 2
 2
 3 4