Lập Kế Hoạch Du Lịch

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ trang trại và $K$ trạm trung chuyển (hub). Trạm trung chuyển là một tập con $K$ trang trại đầu tiên (trang trại $1$ đến $K$ ). Có $M$ chuyến bay một chiều giữa các trang trại, mỗi chuyến bay từ trang trại $u$ đến trang trại $v$ với chi phí $d$ .

Cho $Q$ yêu cầu di chuyển, mỗi yêu cầu từ trang trại $a$ đến trang trại $b$ . Một hành trình hợp lệ phải đi qua ít nhất một trạm trung chuyển (tức là tồn tại một trạm $h$ ( $1 \leq h \leq K$ ) sao cho có đường đi từ $a$ đến $h$ và từ $h$ đến $b$ ).

Với mỗi yêu cầu, tìm chi phí nhỏ nhất để đi từ $a$ đến $b$ qua ít nhất một trạm trung chuyển. Nếu không có hành trình hợp lệ nào, bỏ qua yêu cầu đó.

Dữ liệu vào

Dòng 1: Bốn số nguyên $N$ , $M$ , $K$ , $Q$ .
$M$ dòng tiếp theo: Mỗi dòng gồm ba số nguyên $u_{i}$ , $v_{i}$ , $d_{i}$ — chuyến bay từ trang trại $u_{i}$ đến $v_{i}$ với chi phí $d_{i}$ .
$Q$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $a_{i}$ , $b_{i}$ — yêu cầu di chuyển từ $a_{i}$ đến $b_{i}$ .

Dữ liệu ra

Dòng 1: Số lượng yêu cầu có hành trình hợp lệ.
Dòng 2: Tổng chi phí nhỏ nhất của tất cả các yêu cầu hợp lệ.

Ràng buộc

$1 \leq N \leq 200$
$1 \leq K \leq 100$ , $K \leq N$
$1 \leq M \leq 10 000$
$1 \leq d_{i} \leq 1 000 000$
$1 \leq Q \leq 10 000$

Ví dụ

Input	Output	Giải thích
3 3 1 3 3 1 10 1 3 10 1 2 7 3 2 2 3 1 2	2 24	Hub duy nhất là trang trại 1. Yêu cầu 3→2: đi 3→1→2 tốn 10+7=17. Yêu cầu 2→3: không có đường qua hub 1. Yêu cầu 1→2: đi 1→2 tốn 7. Tổng: 2 yêu cầu hợp lệ, chi phí 24.

Ghi chú

Cần xét mọi trạm trung chuyển có thể để tìm chi phí tối thiểu. Chi phí từ $a$ đến $b$ qua hub $h$ là $dist (a, h) + dist (h, b)$ .

Bình luận

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