Khám phá bí mật trên đảo
Đề bài
Mô tả
Có nhiều làng, một số cặp làng được nối với nhau bằng đường hai chiều. Một lữ khách xuất phát từ một làng (làng nguồn) và cần đi đến một làng định trước (làng đích). Để làm vậy, lữ khách đi theo các con đường qua các làng cho đến khi tới làng đích. Ở mỗi làng lữ khách có thể tìm thấy một số viên đá mặt trăng. Mỗi con đường có một chi phí đi lại.
Hãy tìm đường đi cho lữ khách sao cho tổng chi phí là nhỏ nhất. Nếu có nhiều đường đi cùng chi phí nhỏ nhất, chọn đường đi thu được nhiều đá mặt trăng nhất (lữ khách nhặt đá ở mọi làng trên đường đi, kể cả làng nguồn và làng đích).
Tổng chi phí ảnh hưởng của làng , ký hiệu , là tổng chi phí ảnh hưởng của mọi làng thuộc lân cận bậc của làng . Lân cận bậc của không chứa chính . Với hai làng khác nhau và , làng thuộc lân cận bậc của khi và chỉ khi có thể đi từ đến qua không quá con đường.
Chi phí đi từ làng sang làng kề theo con đường là:
trong đó nối với , là tổng chi phí ảnh hưởng của và là chi phí của con đường .
Các làng có tên đôi một khác nhau, mỗi tên gồm đúng bốn chữ cái in thường.
Dữ liệu vào
- Dòng đầu tiên chứa ba số , , : số làng, số con đường và giá trị dùng để định nghĩa lân cận.
- Dòng thứ hai chứa tên làng nguồn và tên làng đích.
- dòng tiếp theo, mỗi dòng mô tả một làng: tên làng, số đá mặt trăng của làng và chi phí ảnh hưởng của làng.
- dòng cuối, mỗi dòng mô tả một con đường: tên hai làng ở hai đầu và chi phí của con đường.
Dữ liệu ra
In ra chi phí nhỏ nhất và số đá mặt trăng lớn nhất, cách nhau một dấu cách.
Ràng buộc
- .
- .
- .
- .
- .
- .
- Làng nguồn khác làng đích và luôn có đường đi từ làng nguồn đến làng đích.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 4 0 nagi nage nagi 5 1 nagf 7 2 nagh 2 2 nagd 6 5 nagg 5 2 nage 2 5 nagh nagd 96 nagi nagh 25 nagh nagg 49 nagd nage 3 |
124 15 | nên mọi bằng . Đường đi nagi, nagh, nagd, nage có chi phí và viên đá. |
| 4 2 1 akko akkm akko 2 5 akkp 8 2 akkn 1 1 akkm 6 3 akkn akkm 20 akko akkn 3 |
32 9 | (chỉ có akkn kề), . Chi phí , số đá . |
| 6 5 2 gaam gaak gaak 2 1 gaan 2 3 gaaj 1 2 gaao 5 5 gaal 1 2 gaam 1 3 gaan gaaj 96 gaao gaal 25 gaak gaao 95 gaan gaal 37 gaaj gaam 89 |
384 12 | Đường đi duy nhất là gaam, gaaj, gaan, gaal, gaao, gaak. Tổng chi phí đường là , tổng của năm làng được rời đi là . |
Bình luận