Tìm tuyến xe bus có số cước nhỏ nhất

[hieu12 (孝 中)]

Các bác bày cho em bài này với:
A lần đầu đến X và muốn đón duy nhất 1 tuyến xe bus để đi từ địa điểm 𝐴 đến địa điểm 𝐵. Khu X gồm 𝑛(𝑛 ≤ 500) tuyến xe bus, mỗi tuyến có một lộ trình riêng biệt gồm từ 2 địa điểm trở lên và không quay lại địa điểm đã đi qua. Giá cước của mỗi tuyến được tính trọn gói cho hành khách lên và xuống xe tại bất kỳ 2 địa điểm nào của lộ trình (giá cước không giảm cho dù hành khách đi đoạn đường ngắn hơn trên lộ trình).
Dữ liệu:

• Dòng đầu tiên chứa 3 số nguyên dương 𝐴, 𝐵, 𝑛
• Trong 2 × 𝑛 dòng tiếp theo mô tả từng lộ trình của các tuyến xe bus, mỗi tuyến trên 2 dòng: dòng đầu tiên chứa số nguyên 𝑐(1 ≤ 𝑐 ≤ 1000) là giá cước của lộ trình và 𝑚(1 ≤ 𝑚 ≤ 500) là số địa điểm của lộ trình; dòng tiếp theo chứa dãy số nguyên 𝑥1, 𝑥2, … , 𝑥𝑚(1 ≤ 𝑥𝑖 ≤ 100000) là danh sách các địa điểm mà tuyến xe đi qua theo đúng thứ tự đó.
  Kết quả: một số nguyên là giá cước thấp nhất mà A phải trả hoặc -1 nếu như không tìm được lộ trình nào để đi từ 𝐴 đến 𝐵 chỉ bằng 1 tuyến xe duy nhất.

[kisuluoibieng (Tên Gì Cũng Được)]

Bài này dùng mảng 2 chiều ghi lại chi phí rẻ nhất giữa tất cả các cặp điểm (chỉ đi 1)
Ví dụ tuyến a - b - c - d, giá vé là 2, thì ghi nhận chi phí ab, ac, ad, bc, bd, cd là 2
Sau đó b - f - c, giá 1 thì ghi nhận bf, bc, fc là 1 (trong đó bc được update giá từ 2 thành 1)
Sau đí có tuyếb a - d - x giá vé 3 thì ghi nhận ax, dx giá 3 (ngòai ra có ad nữa nhưng chi phí lớn hơn so với ad của tuyến 1,nên không ghi nhận)

Sau đó dựa vào các thuật toán tìm chi phí rẻ nhất (hay thường được lấy vị dụ là đường đi ngắn nhất) khi tìm đường đi của đồ thị, ví dụ như Dijkstra (đầy ví dụ trên mạng)

Update, nếu là dùng Dijkstra thì tổ chức dữ liệu bằng danh sách cạnh kề sẽ tốt hơn, nhưng bài này dùng danh sách cạnh kề thì chi phí đọc (và tối ưu ban đầu) sẽ tăng hơn rất nhiều. Dù sao dùng ma trận kề vẫn là đơn giản hơn, nên thử trước