trang chủ / đề bài / icpc21_bt_d

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 v, ký hiệu ct(v), là tổng chi phí ảnh hưởng của mọi làng thuộc lân cận bậc k của làng v. Lân cận bậc k của v không chứa chính v. Với hai làng khác nhau u và v, làng u thuộc lân cận bậc k của v khi và chỉ khi có thể đi từ v đến u qua không quá k con đường.

Chi phí đi từ làng vs sang làng kề va theo con đường r là:

chi phí=ct(vs)+cr

trong đó r nối vs với va, ct(vs) là tổng chi phí ảnh hưởng của vs và cr là chi phí của con đường r.

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ố N, M, k: số làng, số con đường và giá trị k 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.
  • N dòng tiếp theo, mỗi dòng mô tả một làng: tên làng, số đá mặt trăng m của làng và chi phí ảnh hưởng f của làng.
  • M 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 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

  • 1≤N≤104.
  • 1≤M≤104.
  • 0≤k≤5.
  • 1≤c≤99.
  • 1≤m≤8.
  • 1≤f≤5.
  • 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 k=0 nên mọi ct bằng 0. Đường đi nagi, nagh, nagd, nage có chi phí 25+96+3=124 và 5+2+6+2=15 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 ct(akko)=1 (chỉ có akkn kề), ct(akkn)=5+3=8. Chi phí (1+3)+(8+20)=32, số đá 2+1+6=9.
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à 342, tổng ct của năm làng được rời đi là 5+8+12+11+6=42.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0