Chi phí đường đi tối thiểu

Trong một dự án mới, FullHouse Dev được giao nhiệm vụ phát triển hệ thống tối ưu hóa cho mạng lưới đường sắt. Với kinh nghiệm trong việc xử lý các bài toán phức tạp, nhóm bắt tay vào phân tích và tìm giải pháp tối ưu cho hệ thống đường ray xe lửa.

Bài toán

FullHouse Dev được cung cấp \(N\) ga xe lửa và \(M\) đường ray hai chiều kết nối trực tiếp giữa các ga. Mỗi kết nối trực tiếp giữa ga \(u\) và \(v\) cho phép tàu di chuyển trực tiếp giữa hai ga này mà không cần đi qua ga trung gian nào.

Mỗi đoạn đường ray có độ dài \(D\) km và tàu di chuyển với tốc độ 1 km/phút. Thời gian dừng tại các ga được coi là không đáng kể. Nhiệm vụ của nhóm là tính toán đường đi ngắn nhất giữa hai ga bất kỳ.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) - số lượng ga và số lượng đường ray kết nối.
• Dòng thứ hai chứa \(N\) chuỗi ký tự - tên của các ga.
• \(M\) dòng tiếp theo, mỗi dòng chứa hai chuỗi ký tự Station1, Station2 và một số nguyên \(D\) - thể hiện có đường ray kết nối trực tiếp giữa Station1 và Station2 với độ dài \(D\) km.
• Dòng tiếp theo chứa số nguyên \(Q\) - số lượng truy vấn.
• \(Q\) dòng cuối cùng, mỗi dòng chứa hai chuỗi ký tự Source và Destination.

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra một số nguyên duy nhất thể hiện chi phí của đường đi ngắn nhất giữa ga nguồn và ga đích.

Ràng buộc:

• \(1 \leq N \leq 100\)
• \(1 \leq M \leq N * (N - 1) / 2\)
• \(1 \leq Q \leq N * (N - 1) / 2\)

Ví dụ

INPUT

4 4
Howrah Trivandram Vashi Mysore
Howrah Trivandram 10
Howrah Vashi 20
Trivandram Mysore 100
Mysore Vashi 50
6
Howrah Trivandram
Howrah Vashi
Howrah Mysore
Trivandram Vashi
Trivandram Mysore
Mysore Vashi

OUTPUT

10
20
70
30
80
50

Giải thích

• Truy vấn 1: Đường đi ngắn nhất là Howrah -> Trivandram với tổng độ dài 10.
• Truy vấn 2: Đường đi ngắn nhất là Howrah -> Vashi với tổng độ dài 20.
• Truy vấn 3: Đường đi ngắn nhất là Howrah -> Vashi -> Mysore với tổng độ dài 20 + 50 = 70.
• Truy vấn 4: Đường đi ngắn nhất là Trivandram -> Howrah -> Vashi với tổng độ dài 10 + 20 = 30.
• Truy vấn 5: Đường đi ngắn nhất là Trivandram -> Howrah -> Vashi -> Mysore với tổng độ dài 10 + 20 + 50 = 80.
• Truy vấn 6: Đường đi ngắn nhất là Mysore -> Vashi với tổng độ dài 50.