2. Di chuyển robot (Olympic 30/4 K11 - 2024)
Một cuộc thi lập trình điều khiển robot được ban tổ chức olympic 30-4 thiết kế cho các bạn yêu thích Tin học. Ban tổ chức thiết kế một sơ đồ cho robot di chuyển gồm \(n\) địa điểm được đánh số từ 1 tới \(n\) và được nối với nhau bởi \(m\) con đường hai chiều, đánh số từ 1 tới \(m\). Con đường thứ \(i\) nối hai địa điểm \(u_i\) và \(v_i\) với trọng số \(w_i\ (1≤u_i,v_i≤n;w_i≤10^9)\). Tại mỗi địa điểm ghi một số nguyên \(a_i\) là số điểm thưởng mà robot nhận được khi đến địa điểm này lần đầu.
Ban tổ chức chọn một địa điểm \(s\) làm địa điểm xuất phát và robot nhận được điểm thưởng đầu tiên tại địa điểm này. Mỗi khi đi qua con đường có trọng số lớn hơn điểm thưởng đang có, robot sẽ nhận một thẻ phạt. Robot được phép bị phạt không quá \(k\) thẻ. Khi bị phạt thẻ, robot sẽ không được phép nhận thêm điểm thưởng ở bất kỳ địa điểm nào nữa.
Yêu cầu: Hãy xác định số địa điểm lớn nhất mà robot có thể đi qua.
Input
- Dòng đầu tiên chứa 4 số nguyên \(n,m,s\) và \(k\ (1≤n≤10^5;1≤m≤2×10^5; 1≤s≤n;k≤1)\);
- Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n\ (1≤a_i≤10^9 )\);
- Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa 3 số nguyên \(u_i,v_i\) và \(w_i\ (1≤u_i≠v_i≤n;1≤w_i≤10^9)\).
Output
- Một số nguyên duy nhất là số địa điểm tối đa mà robot có thể đi qua.
Scoring
- \(30\%\) số điểm có \(m=n-1<10^3;u_i=i; v_i=i+1;k=0\);
- \(20\%\) số điểm có \(k=0;n≤10^3\);
- \(20\%\) số điểm có \(k=0;n≤10^5\);
- \(30\%\) số test có \(k=1\).
Example
Test 1
Input
6 7 3 1
3 4 2 3 2 7
1 6 10
1 5 8
5 2 12
2 6 10
2 3 5
3 4 1
3 5 11 Output
5Note
Robot đi \(3→4→3→2→5→1\). Robot đi \(3→4→3→2\) nhận được điểm thưởng là 9. Đi từ 2 sang 5 bị nhận 1 thẻ phạt và từ đó không được nhận thêm điểm thưởng.