#1299 · Tô màu đồ thị

Lập trình cá nhân tháng 2s 128MB

Đăng nhập

MÔ TẢ BÀI TOÁN

Bạn được cho một đồ thị có hướng, cạnh có trọng số. Trong đó, một số đỉnh được tô màu đen.

Cho 2 đỉnh $s$ và $t$ $(s \neq t)$ . Hãy tìm đường đi có chi phí ít nhất từ $s$ đến $t$ thỏa mãn:

Gọi $w(e)$ là trọng số của cạnh $e$ . Với bất kì $2$ cạnh $x, y$ kề nhau trên đường đi: $0.5 \times w(x) \leq w(y) \leq 2 \times w(x)$
Đường đi từ $s$ đến $t$ phải có chính xác $1$ lần xuất hiện của $1$ đỉnh được tô màu đen.

Dòng đầu tiên gồm 2 số nguyên $n$ và $m$ $(1 \leq n \leq 10^5, 1 \leq m \leq 5 \times 10^5$ ) — số đỉnh và số cạnh của đồ thị.
$m$ dòng tiếp theo, dòng thứ $i$ gồm $3$ số nguyên $u_i, v_i, w_i (1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9)$ — biểu diễn một cạnh có hướng từ $u$ đến $v$ với trọng số là $w$ .
Dòng tiếp theo sau đó gồm $1$ số nguyên $k$ $(1 \leq k \leq n)$ — số lượng đỉnh được tô màu đen.
Dòng tiếp theo gồm $k$ số nguyên $a_j$ $(1 \leq a_j \leq n)$ — chỉ số của đỉnh được tô màu đen.
Dòng cuối cùng gồm $2$ số nguyên $s$ và $t (1 \leq s, t \leq n, s \neq t)$ — Đỉnh bắt đầu và đỉnh kết thúc.

Lưu ý: Đồ thị có thể có nhiều hơn $1$ cạnh giữa $2$ đỉnh bất kì và đảm bảo không có cạnh nối $1$ nút đến chính nó.

Nếu không có đường đi từ $s$ đến $t$ thỏa mãn, in ra $-1$ . Nếu có, in ra giá trị đường đi hợp lệ có chi phí ít nhất từ $s$ đến $t$ .

#	Tài khoản	Kết suất	Lúc nộp
1	T Nguyễn Tri Bão Thắng @2180601452	753 ms 58928 KB 7033 Bytes	03/06/2023 19:46
2	Nguyễn Tri Bão Thắng @25807700104	844 ms 57932 KB 2605 Bytes	23/12/2025 15:28
3	T Nguyễn Trung Tuyến @2011064511	1110 ms 35448 KB 3429 Bytes	13/09/2025 19:24
4	Lê Duy Hải @2280600799	1640 ms 102288 KB 3588 Bytes	19/01/2025 11:35
5	Lê Duy Hải @2280600799	1650 ms 102280 KB 3588 Bytes	19/01/2025 11:37
6	Lê Duy Hải @2280600799	1661 ms 102280 KB 3588 Bytes	19/01/2025 11:37
7	GV. Bùi Phú Khuyên @KBP0100298	1951 ms 102248 KB 1866 Bytes	23/03/2023 14:45

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

Chưa có thảo luận nào cho bài này.

Trong ví dụ $1$ , đường đi $1-3-4$ là $1$ đường đi hợp lệ với chi phí $2$ và có chính xác $1$ đỉnh được tô màu đen là đỉnh $4$ . Tuy $1-2-3-4$ cũng là $1$ đường đi hợp lệ, nhưng chi phí của đường đi là $3$ . Vậy nên $2$ là chi phí ít nhất của đường đi thỏa mãn.
Trong ví dụ $2$ , đầu tiên mình đi qua cạnh $1-2$ với chi phí là $3$ . Tuy có cạnh $2-3$ với chi phí là $1$ , nhưng do $0.5 \times 3 > 1$ , nên chúng ta không thể chọn cạnh này được. Nên chỉ còn cách chọn cạnh $2-3$ với chi phí là $3$ . Kết quả là $3 + 3 = 6$ .
Trong ví dụ $3$ , không có đường đi hợp lệ từ $1$ đến $4$ , nên chúng ta in ra $-1$ .

Đang chạy thử nghiệm...

Vui lòng chờ tiến trình hoàn tất

KIỂM THỬ

Không có dữ liệu kiểm thử