trang chủ / đề bài / icpc24_mt_m

Giải chạy marathon

Đề bài

Mô tả

Năm nay, một kỳ thi ICPC khu vực sẽ được tổ chức tại Hà Nội. Bên cạnh cuộc thi rất khó để chọn ra các đội vào chung kết thế giới, ban tổ chức quyết định tổ chức thêm một giải chạy marathon để các thí sinh có dịp khám phá vẻ đẹp của Hà Nội.

Địa điểm tổ chức giải marathon gồm n nút giao, đánh số từ 1 đến n. Có m con đường hai chiều, đánh số từ 1 đến m; con đường thứ i nối hai nút giao ui và vi và có độ dài li. Các con đường đảm bảo luôn đi được giữa mọi cặp nút giao.

Giải marathon gồm nhiều lượt chạy. Trong mỗi lượt, các vận động viên xuất phát ở một nút giao, chạy qua một số con đường và về đích ở một nút giao khác. Mọi vận động viên chạy cùng một lộ trình do ban tổ chức chọn. Các điều kiện sau đúng với mọi lượt:

  • Có ít nhất một lượt chạy.
  • Trong mọi lượt, nút xuất phát khác nút về đích.
  • Nút xuất phát của mỗi lượt trùng với nút về đích của lượt trước đó.
  • Trong mọi lượt, ban tổ chức luôn chọn một đường đi ngắn nhất từ nút xuất phát đến nút về đích. Đường đi ngắn nhất là đường đi có tổng độ dài các con đường nhỏ nhất có thể.

Ban tổ chức định nghĩa tập độ khó của giải là tập các giá trị phân biệt của độ dài các lượt chạy. Cụ thể, một giải gồm k lượt có thể biểu diễn bằng dãy nút giao x0,x1,…,xk, trong đó lượt thứ i xuất phát ở xi−1 và về đích ở xi. Gọi d(a,b) là độ dài đường đi ngắn nhất từ nút a đến nút b. Tập độ khó của giải là tập các giá trị xuất hiện ít nhất một lần trong dãy d(x0,x1),d(x1,x2),…,d(xk−1,xk).

Để giải thêm thú vị, ban tổ chức có q phương án. Mỗi phương án là một tập số s1,s2,…,sc, và ban tổ chức muốn biết có thể tổ chức một giải có tập độ khó đúng bằng tập này hay không.

Hãy giúp ban tổ chức có một kỳ thi ICPC thật tuyệt vời!

Dữ liệu vào

Dòng đầu tiên chứa số nguyên θ, số bộ dữ liệu. Tiếp theo là θ bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên là một dòng trống.
  • Dòng thứ hai chứa ba số nguyên n, m, q (1≤n≤400, 0≤m≤n(n−1)2, 1≤q≤2·105): số nút giao, số con đường và số phương án.
  • m dòng tiếp theo, dòng thứ i chứa ba số nguyên ui, vi, li (1≤ui,vi≤n, 1≤li≤104) mô tả con đường thứ i.
  • q dòng cuối, mỗi dòng chứa số nguyên c (1≤c≤2·105) và theo sau là c số nguyên s1,s2,…,sc (1≤s1<s2<…<sc≤107) mô tả một phương án.

Dữ liệu đảm bảo:

  • Tổng n trên mọi bộ dữ liệu không vượt quá 1600.
  • Tổng c trên mọi phương án của mọi bộ dữ liệu không vượt quá 8·105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng gồm đúng q từ. Từ thứ i là câu trả lời cho phương án thứ i: Yes nếu có thể tổ chức được giải như vậy, No nếu không.

Ràng buộc

  • 1≤n≤400, 0≤m≤n(n−1)2, 1≤li≤104; mọi cặp nút giao đều đi được đến nhau.
  • 1≤q≤2·105, 1≤c≤2·105, 1≤s1<s2<…<sc≤107.
  • Tổng n không vượt quá 1600, tổng c không vượt quá 8·105.

Ví dụ

Input Output Giải thích
2

5 4 3
3 4 1
2 1 2
3 2 3
4 5 4
2 1 2
2 3 4
3 3 4 8

5 4 3
3 4 1
2 1 2
3 2 3
4 5 4
2 4 6
2 3 5
3 4 5 6
No Yes Yes
Yes Yes Yes
Bộ thứ nhất, phương án 2: giải 3→2→4 có d(3,2)=3, d(2,4)=4. Phương án 3: giải 3→2→4→5→2 có d(3,2)=3, d(2,4)=d(4,5)=4, d(5,2)=8. Phương án 1: chỉ có cặp (3,4) cách nhau 1 và cặp (1,2) cách nhau 2, không nối tiếp được.
3

1 0 3
1 1
2 1 2
1 10000000

3 3 3
1 2 1
2 3 1
1 3 1
1 1
1 2
2 1 2

3 2 4
1 2 1
2 3 1
1 1
1 2
2 1 2
1 3
No No No
Yes No No
Yes Yes Yes No
Bộ thứ nhất chỉ có một nút giao nên không có lượt chạy nào. Bộ thứ hai là tam giác cạnh 1: mọi khoảng cách đều bằng 1. Bộ thứ ba là đường 1−2−3: giải 1→2→1→3 có tập độ khó {1,2}.

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