Switch Grass

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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$ cánh đồng và $M$ con đường hai chiều. Mỗi cánh đồng trồng một trong $K$ loại cỏ. Đôi khi Farmer John quyết định thay đổi loại cỏ của một cánh đồng. Sau mỗi thay đổi, hãy tìm khoảng cách ngắn nhất giữa hai cánh đồng có loại cỏ khác nhau.

Khoảng cách giữa hai cánh đồng là độ dài đường đi ngắn nhất nối chúng.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên $N$ , $M$ , $K$ , $Q$ .

$M$ dòng tiếp theo, mỗi dòng ba số nguyên $A$ , $B$ , $L$ : con đường hai chiều giữa cánh đồng $A$ và $B$ với độ dài $L$ .

Dòng tiếp theo chứa $N$ số nguyên: loại cỏ ban đầu của mỗi cánh đồng (từ $1$ đến $K$ ).

$Q$ dòng tiếp theo, mỗi dòng hai số nguyên $A$ , $B$ : thay đổi loại cỏ cánh đồng $A$ thành loại $B$ .

Dữ liệu ra

In $Q$ dòng, dòng thứ $i$ là khoảng cách ngắn nhất giữa hai cánh đồng có loại cỏ khác nhau sau lần cập nhật thứ $i$ .

Ràng buộc

$1 \leq N, M, K, Q \leq 2 \times 10^{5}$
$1 \leq L \leq 10^{6}$
Luôn tồn tại ít nhất hai cánh đồng có loại cỏ khác nhau
Không có hai con đường cùng nối một cặp cánh đồng
30% test: mỗi cánh đồng có bậc không quá 10

Ví dụ

Input	Output	Giải thích
3 2 3 4 1 2 3 2 3 1 1 1 2 3 3 2 3 1 2 2 2	1 3 3 1	Sau lần 1: cánh đồng 1→loại 1, 2→loại 1, 3→loại 2. Cạnh 2-3 (độ dài 1) nối hai loại khác nhau → đáp án 1. Sau lần 2: 1→loại 1, 2→loại 3, 3→loại 2. Tất cả cạnh đều nối hai loại khác → min là 1, nhưng sau lần 3: 1→loại 2, 2→loại 3, 3→loại 2, cạnh 1-2 dài 3 → đáp án 3.

Bình luận

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