trang chủ / đề bài / icpcwf21_b

Khám phá hầm ngục

Đề bài

Mô tả

Alice và Bob phụ trách chạy thử một phòng thoát hiểm mới! Trong phòng thoát hiểm này, người chơi bị nhốt trong một hầm ngục và phải khám phá toàn bộ khu vực.

Hầm ngục gồm n phòng được nối với nhau bởi đúng n−1 hành lang. Có thể đi giữa hai phòng bất kỳ bằng các hành lang này.

Hai trong số các phòng là phòng đặc biệt. Một phòng chứa một bảo vật hộ mệnh gọi là "chìa khoá xoắn". Một phòng khác chứa một "bẫy vòm" nguy hiểm: khi bẫy kích hoạt, người chơi không thể di chuyển nữa. Nếu đi vào phòng có bẫy trước khi lấy được chìa khoá, người chơi sẽ bị nhốt trong hầm ngục mãi mãi. Người chơi không bắt đầu ở phòng có chìa khoá hay phòng có bẫy.

Có q tình huống khác nhau mà Alice và Bob muốn xem xét. Trong tình huống thứ i, người chơi bắt đầu ở phòng si, chìa khoá ở phòng ki và bẫy ở phòng ti. Với mỗi tình huống, hãy tính thời gian nhỏ nhất cần thiết để khám phá toàn bộ hầm ngục mà không bị mắc bẫy.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên n và q: số phòng và số tình huống cần xét. Các phòng được đánh số từ 1 đến n.
  • n−1 dòng tiếp theo, mỗi dòng gồm ba số nguyên u, v, w cho biết có một hành lang nối phòng u và phòng v (u≠v), đi qua hành lang này mất thời gian w.
  • q dòng tiếp theo, dòng thứ i gồm ba số nguyên đôi một khác nhau si, ki, ti: phòng người chơi bắt đầu, phòng có chìa khoá và phòng có bẫy.

Dữ liệu ra

Với mỗi tình huống, in ra trên một dòng thời gian nhỏ nhất cần thiết để đi qua mọi phòng ít nhất một lần. Nếu không thể đi qua mọi phòng, in ra impossible.

Ràng buộc

  • 3≤n≤2000, 1≤q≤200000.
  • 1≤u,v≤n, u≠v, 1≤w≤109.
  • 1≤si,ki,ti≤n, ba số si, ki, ti đôi một khác nhau.

Ví dụ

Hầm ngục của ví dụ thứ nhất (số trên cạnh là thời gian đi qua hành lang):

graph weighted
1 2 3
1 3 1
3 4 4
3 5 2
Input Output Giải thích
5 4
1 2 3
1 3 1
3 4 4
3 5 2
1 2 4
1 4 2
5 2 1
4 3 1
15
17
impossible
12
Tình huống 1: đi 1→2→1→3→5→3→4, mất 3+3+1+2+2+4=15. Tình huống 2: phải lấy chìa khoá ở phòng 4 trước khi vào phòng 2, đi 1→3→5→3→4→3→1→2, mất 17. Tình huống 3: mọi đường từ phòng 5 tới phòng 2 đều qua phòng 1 có bẫy. Tình huống 4: đi 4→3→5→3→1→2, mất 12.
7 4
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 2 3
5 4 1
3 1 4
2 4 5
11
impossible
10
10
Hình sao tâm 1, mọi hành lang dài 1. Tình huống 2: bẫy ở tâm 1, không thể tới phòng 4 có chìa khoá. Tình huống 3: đi từ phòng 3 qua tâm (lấy chìa khoá), thăm lần lượt các phòng lá còn lại và dừng ở phòng lá cuối cùng, mất 10.

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