JOI 2024 - Construction Project 2 - LQDOJ: Le Quy Don Online Judge

JOI 2024 - Construction Project 2

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1800 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Vương quốc JOI có \(N\) nhà ga, được đánh số từ \(1\) đến \(N\), và \(M\) tuyến đường sắt, được đánh số từ \(1\) đến \(M\). Tuyến đường sắt \(i\) (\(1 \le i \le M\)) nối hai chiều giữa ga \(A_i\) và ga \(B_i\), với thời gian di chuyển là \(C_i\) phút.

Là một vị bộ trưởng của vương quốc JOI, bạn quyết định xây thêm đúng một tuyến đường sắt như sau: chọn hai số nguyên \(u,v\) thỏa mãn \(1 \le u<v \le N\), rồi xây một tuyến nối hai chiều giữa ga \(u\) và ga \(v\), với thời gian di chuyển là \(L\) phút. Bạn được phép chọn hai ga đã có tuyến đường sắt nối trực tiếp với nhau.

Sau khi tuyến mới được xây dựng, nhà vua sẽ vui nếu có thể đi từ ga \(S\) đến ga \(T\) bằng các tuyến đường sắt trong thời gian không quá \(K\) phút. Không tính thời gian chờ tàu hay chuyển tuyến.

Có \(\frac{N(N-1)}{2}\) cách chọn hai số \(u,v\). Cho thông tin về các nhà ga, các tuyến đường sắt và yêu cầu của nhà vua, hãy đếm số cách chọn làm nhà vua vui.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N M
S T L K
A_1 B_1 C_1
A_2 B_2 C_2
...
A_M B_M C_M

Dữ liệu ra

In ra một dòng chứa số cách chọn hai số nguyên \(u,v\) làm nhà vua vui.

Ràng buộc

\(2 \le N \le 200\,000\).
\(1 \le M \le 200\,000\).
\(1 \le S<T \le N\).
\(1 \le L \le 10^9\).
\(1 \le K \le 10^{15}\).
\(1 \le A_i<B_i \le N\) (\(1 \le i \le M\)).
\((A_i,B_i) \ne (A_j,B_j)\) (\(1 \le i<j \le M\)).
\(1 \le C_i \le 10^9\) (\(1 \le i \le M\)).
Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

8 điểm: \(L=1\), \(K=2\), \(C_i=1\) với mọi \(1 \le i \le M\).
16 điểm: \(N \le 50\), \(M \le 50\).
29 điểm: \(N \le 3\,000\), \(M \le 3\,000\).
47 điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Chẳng hạn, chọn \(u=3\), \(v=6\). Một tuyến đường sắt hai chiều giữa ga \(3\) và ga \(6\), với thời gian di chuyển \(1\) phút, sẽ được xây dựng.

Khi đó, có thể đi từ ga \(6\) đến ga \(7\) trong \(2\) phút như sau:

Đi từ ga \(6\) đến ga \(3\) bằng tuyến mới nối hai ga này, mất \(1\) phút.
Đi từ ga \(3\) đến ga \(7\) bằng tuyến nối hai ga này, mất \(1\) phút.

Nhà vua vui vì có thể đi từ ga \(6\) đến ga \(7\) trong thời gian không quá \(2\) phút. Tính cả cách trên, có \(4\) cách chọn hai số nguyên làm nhà vua vui, nên in ra 4.

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,3,4\).

Ví dụ 2

Input

Output

Giải thích

Dù chọn hai số nguyên như thế nào, nhà vua cũng vui. Có \(3\) cách chọn, vì vậy in ra 3.

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,3,4\).

Ví dụ 3

Input

6 4
2 5 1000000000 1
1 2 1000000000
2 3 1000000000
2 4 1000000000
5 6 1000000000

Output

Giải thích

Không có cách chọn hai số nguyên nào làm nhà vua vui, vì vậy in ra 0.

Ví dụ này thỏa mãn ràng buộc của các nhóm \(2,3,4\).

Ví dụ 4

Input

18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(2,3,4\).

Nguồn

Construction Project 2, JOI 2024, vòng chung kết quốc gia, bài 2 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

JOI 2024 - Vòng chung kết quốc gia (4 Tháng 2., 2024)