Bessla Motors

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.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

Nong dan John muon xac dinh cac diem den co ket noi tot voi mang luoi tram sac Bessla. Co $N$ diem, trong do $C$ diem dau tien la tram sac, cac diem con lai la diem den. Cac diem duoc noi boi $M$ con duong hai chieu, moi duong co do dai $ℓ_{i}$ . Xe Bessla co the di toi da $R$ dam tu mot tram sac.

Mot diem den duoc goi la "ket noi tot" neu co the di den tu it nhat $K$ tram sac khac nhau (moi lan xuat phat tu tram voi binh day).

Hay dem so diem den ket noi tot va liet ke chung.

Du lieu vao

Dong 1: Nam so nguyen $N$ , $M$ , $C$ , $R$ , $K$ .
$M$ dong tiep theo: Ba so nguyen $u_{i}$ , $v_{i}$ , $ℓ_{i}$ -- duong noi $u_{i}$ va $v_{i}$ voi do dai $ℓ_{i}$ .

Du lieu ra

Dong 1: So luong diem den ket noi tot.
Cac dong tiep theo: Chi so cac diem den (tang dan).

Rang buoc

$2 \leq N \leq 50000$
$1 \leq M \leq 100000$
$1 \leq C < N$
$1 \leq R, ℓ_{i} \leq 10^{9}$
$1 \leq K \leq 10$

Vi du

Input	Output	Giai thich
3 3 1 4 1 1 2 3 1 3 5 2 3 2	1 2	1 tram sac (dinh 1). Dinh 2 cach 3 ( $\leq 4$ ): ket noi. Dinh 3 cach 5 ( $> 4$ ): khong.
4 4 2 101 2 1 3 100 2 3 100 1 4 100 2 4 100	2 3 4	2 tram sac (dinh 1, 2). Ca dinh 3 va 4 deu cach ca 2 tram $\leq 101$ .

Bình luận

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