Cessla

Xem dạng PDF
Gửi bài giải
Điểm: 0,60 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Châu đang muốn quảng bá dòng xe điện Cessla của mình bằng cách giới thiệu mạng lưới các trạm sạc của Cessla. Anh ấy đã xác định được ~N (2 \le N \le 5*10^4)~ điểm quan tâm được đánh số từ ~1~ đến ~N~, trong đó ~C(1 \le C \le N)~ trạm đầu tiên là các trạm sạc và còn lại là các điểm du lịch. Các điểm này được kết nối với nhau bởi ~M(1\le M \le 10^5)~ đường hai chiều, đường thứ ~i~ nối hai điểm phân biệt ~u_i~ và ~v_i~ và có độ dài ~l_i~ dặm ~(1\le l_i \le 10^9)~.

Cessla có thể di chuyển với quãng đường lên tới ~2R~ dặm ~(1 \le R \le 10^9)~ trong một lần sạc, cho phép nó đến bất kỳ điểm đến nào trong phạm vi ~R~ dặm tính từ trạm sạc. Một điểm đến được coi là kết nối tốt nếu có thể đến được điểm đến đó từ ít nhất ~K(1\le K\le 10)~ trạm sạc riêng biệt. Nhiệm vụ của bạn là hỗ trợ John xác định các điểm đến du lịch có kết nối tốt.

Input

Dòng đầu tiên chứa năm số nguyên ~N,M,C,R,K~. Mỗi dòng trong ~M~ dòng tiếp chứa ba số nguyên cách nhau bằng dấu cách ~u_i,v_i,l_i~ sao cho ~u_i \ne v_i~. Các trạm sạc được đánh số ~1,2,...,C~. Các điểm còn lại đều là các điểm du lịch.

Output

Đầu tiên, in ra số lượng điểm đến du lịch có kết nối tốt trên một dòng. Sau đó, liệt kê tất cả các điểm đến du lịch có kết nối tốt theo thứ tự tăng dần, mỗi điểm trên một dòng riêng biệt.

Scoring

  • Subtask ~1~: ~K=2~, ~N \le 500~ và ~M \le 1000~.
  • Subtast ~2~: ~K=2~.
  • Subtask ~3~: Không có điều kiện gì thêm.

Example

Sample Input 1
3 3 1 4 1
1 2 3
1 3 5
2 3 2
Sample Output 1
1
2
Explanation

Chúng ta có một trạm sạc ở ~1~. Từ trạm sạc này, chúng ta có thể đến điểm ~2~ (vì nó cách ~1~ khoảng cách là ~3~), nhưng không thể đến điểm ~3~ (vì nó cách ~1~ khoảng cách là ~5~). Như vậy chỉ có điểm ~2~ là kết nối tốt.

Sample Input 1
4 3 2 101 2
1 2 1
2 3 100
1 4 10
Sample Output 1
2
3
4
Explanation

Chúng ta có các trạm sạc tại ~1~ và ~2~, và cả hai điểm ~3~ và ~4~ đều cách hai điểm ~1~ và ~2~ khoảng cách là ~101~. Vì vậy, cả hai điểm ~3~ và ~4~ đều có kết nối tốt.

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 1
    TranThienPhuc2657  đã bình luận lúc 14, Tháng 2, 2026, 22:16 ← sửa 12

    Comment này spoil thuật!!

    Các thuật toán mình sử dụng đều là từ tham khảo của các lời giải khác mình tổng hợp lại. Mình sẽ để credit code cho mỗi lời giải mình tham khảo, và mình sẽ để lại code mà mình đã cài đặt lại theo các ý tưởng đó cho các bạn có thể tham khảo được. (Mình mong là các bạn sử dụng code mẫu cho mục đích tham khảo xong rồi làm lại để hiểu, chứ không phải là để copy và có AC, làm như vậy không có ý nghĩa gì).

    Nếu có sai sót gì mong mọi người góp ý cho mình, mình xin cảm ơn!

    Nhận xét chính:

    Xét ~3~ điểm ~s, u, v~. Nếu đường đi ngắn nhất ~s \rightarrow u~ có độ lớn là ~x + 1~ thì nó sẽ không có đóng góp gì cho đường đi ngắn nhất ~s \rightarrow v~ có độ lớn ~\leq x~.

    Chứng minh:

    Gọi: đường đi ngắn nhất ~s \rightarrow u~ có độ lớn là ~x + 1~ là ~P~.

    Ta có: với mọi cách đi nối tiếp ~P~ đi tới ~v~ thì sẽ luôn có ít nhất ~x~ cách đi có độ lớn nhỏ hơn (do ~P~ có độ lớn là ~x + 1~). ~\implies~ Cách đi hiện tại chỉ có thể có độ lớn ~> x~ ~\implies~ không có đóng góp gì cho đường đi ngắn nhất ~s \rightarrow v~ có độ lớn ~\leq x~.

    Lời giải 1:

    Được tham khảo từ code của dex111222333444555

    Tương tự như bài Nhà máy điện, nhưng lần này, thay vì chỉ một cái bao phủ mà cần ít nhất ~K~ cái bao phủ.

    Do ở bài này, mọi ~R~ bằng nhau nên đều có thể cài đặt bằng min heap hay max heap đều được. Ở đây, mình sẽ trình bày cách cài đặt bằng min heap.

    Ý tưởng

    • Do là: độ dài đường đi càng ngắn thì nó sẽ có thể đi được nhiều hơn. ~\implies~ Độ dài đường đi càng ngắn càng tốt ~\implies~ Ta ưu tiên chọn ~K~ độ dài đường đi ngắn nhất có độ dài ~\leq R~.
    • Với nhận xét chính đã được đề cập ở trên, mỗi đỉnh ta chỉ cần lưu tối đa ~K~ đường đi ngắn nhất (Do nếu lưu ~> K~ thì nó cũng sẽ không đóng góp)

    Cài đặt

    Chuẩn bị

    Các cái cần chuẩn bị:

    • Dijkstra của ta lưu ba thông tin: đỉnh hiện tại, khoảng cách tới đỉnh hiện tại (hai cái này như thuật toán Dijkstra bình thường), đỉnh gốc đã đi tới nó.
    • Một vector lưu các đỉnh gốc đã đi tới được đỉnh hiện tại (Mình gọi là vis).

    Đầu tiên, ta sẽ bỏ các cái điểm trạm sạc vào priority_queue với độ dài đường đi bằng ~0~.

    Vòng while của priority_queue

    Do tính chất của min heap nên là cái đỉnh top của priority_queue nó sẽ là ngắn nhất trong mọi cái hiện tại. Do đó, ta sẽ push cái đường đi đó vào.

    Ta cần đảm bảo đường đi tới đỉnh ~u~ thỏa mãn các điều kiện:

    • Độ lớn vis không ~\geq K~ (Nếu thỏa thì nó đã có ~K~ đường đi ngắn nhất rồi)
    • Cái đỉnh gốc chưa từng tới ~u~ (Có thể kiểm tra duyệt hết vis[u] để kiểm tra)

    Nếu mà thỏa thì ta bỏ đỉnh gốc đó vào vis[u].

    Khi mà duyệt các cạnh ~(u, v, w)~, ta có thể đặt nhánh cận kiểm tra đỉnh ~v~ tương tự như trên để tránh bỏ vào quá nhiều đỉnh vào priority_queue, đồng thời cũng kiểm tra xem liệu đường đi có ~\leq R~ không.

    Lấy kết quả

    Cuối cùng, ta kiểm tra xem, liệu đỉnh du lịch ~u~ hiện tại có ~K~ đường đi ngắn nhất không (bằng việc kiểm tra độ lớn mảng vis[u] có bằng ~K~ hay không). Nếu thỏa thì bỏ vào mảng kết quả (res).

    Sau đó, in ra độ lớn mảng res và các đỉnh ở trong res ra.

    Độ phức tạp

    ~\mathcal{O}(K \cdot (N + M) \log_{2} N)~

    Do mỗi đỉnh lưu ~K~ đường đi ngắn nhất nên nhân ~K~ vào trong độ phức tạp của Dijkstra bình thường.

    Tuy vậy, với cách làm này sẽ bị hằng số lớn do là có quá nhiều đỉnh thừa được cho vào priority_queue.

    Theo mình nộp thì cách làm này vừa đủ giới hạn thời gian của bài, gần ~1s~.

    Code mẫu

    ideone

    Lời giải 2:

    Được tham khảo từ code của trandangquang

    Ý tưởng

    • Dijkstra ~K~ lần để mà có ~K~ đường đi ngắn nhất cho mỗi đỉnh như ý tưởng của lời giải 1.
    • Với mỗi lượt thứ ~turn~ thì ta sẽ cho thực hiện Dijkstra trước một cạnh cho tất cả các đỉnh để mà thỏa điều kiện không trùng đỉnh gốc với đỉnh gốc đã có của đỉnh hiện tại. Sau đó thực hiện Dijkstra như bình thường để mà có được độ dài đường đi ngắn nhất lớn thứ ~turn~.

    Cài đặt

    Các mảng sử dụng

    • d[u]: độ dài đường đi ngắn nhất của lượt hiện tại của ~u~ (hay nói cách khác, độ dài đường đi ngắn nhất thứ ~turn~ của ~u~)
    • root[u]: đỉnh gốc của cái đường đi ngắn thứ ~turn~ tới ~u~ đó
    • dp[u][turn]: ở lượt ~turn~, trả về bộ {d[u], root[u]}

    Bước 1

    Đầu tiên, ta Dijkstra đa nguồn để tìm đường đi ngắn thứ nhất cho mọi đỉnh (cái này là một bài toán cơ bản, các bạn có thể tham khảo trên các trang thuật toán nếu không biết làm)

    Với mỗi lượt từ ~2~ tới ~K~, để tìm ra được đường đi ngắn nhất thứ ~turn~, ta lặp lại ~3~ bước ~(2, 3, 4)~ sau.

    Bước 2

    Ta sẽ thực hiện Dijkstra trước 1 cạnh.

    Reset mọi d[u], root[u] về mặc định: d[u] = inf, root[u] = u

    Xét mọi cạnh ~(u, v, w)~, ta sẽ lấy ~\min~ của mọi đường đi ngắn nhất trước đó từ ~u~ nối thêm cạnh hiện tại tới ~v~ và lưu vào d[v], root[v] thỏa mãn: ~root~ của đường đi đó không trùng với ~root~ của các đường đi ngắn nhất trước đó của ~v~. (Do sau mỗi ~turn~, bài toán của ta sẽ là: tìm đường đi ngắn nhất tới đỉnh hiện tại mà không trùng ~root~ với mọi cái đã có nên là ta lấy ~\min~.)

    Bước 3

    Ta thực hiện Dijkstra để tìm ra được độ dài đường đi ngắn nhất thứ ~turn~

    Ở đây, ban đầu, ta sẽ bỏ mọi (d[u], u) vào priority_queue và thực hiện Dijkstra bình thường.

    Bước 4

    Lưu dp[u][turn] = {d[u], root[u]}

    Tính đúng đắn của bước 2 và bước 3

    Trong quá trình nghiên cứu về cách làm này, mình có nghĩ về hai câu hỏi

    Ở bước 2, việc Dijkstra trước một cạnh từ các đường đi ngắn nhất cũ đã là đủ để tìm ra đường đi ngắn nhất thứ ~turn~ chưa, lỡ nó có thể thiếu ~root~?

    Ta sẽ xét hai trường hợp

    • Nối cạnh trực tiếp: xét đường đi ~s \rightarrow u \rightarrow v~, ta có: do cùng đi qua cạnh ~(u, v)~ nên để tối ưu nhất thì: ~s \rightarrow u~ ngắn nhất nên là phải xét một cái đường đi ngắn nhất ~s \rightarrow u~.
    • Đi qua các đỉnh trung gian: do là Dijkstra mới có ~1~ cạnh nên là nó sẽ đi qua các cạnh trung gian nữa để đảm bảo tính đúng đăn. Ở bước này cũng sẽ xuât hiện các cái ~root~ khác nữa nên đảm bảo tính đúng đắn.
    Ở bước 3, liệu việc Dijkstra như vậy sẽ có thể trùng ~root~ của những đỉnh khác không?

    Sử dụng nhận xét chính, ta chứng minh được một khi đỉnh hiện tại không trùng ~root~ nên khi Dijkstra thì mọi đỉnh khác cũng sẽ không trùng ~root~. Đảm báo tính đúng đắn.

    Bước 5

    Lấy kết quả

    Xét xem dp[u][k].first có ~\leq R~ không? Nếu có thì nó thỏa, lưu vào mảng đáp án res

    In độ dài mảng res và in từng phần tử ở trong đó ra.

    Độ phức tạp

    ~\mathcal{O}(K \cdot (M \cdot K^2 + (N + M) \log_2 (N) + N))~

    Tuy là có nhiều bước hơn nhưng mà hằng số Dijkstra nó sẽ nhỏ hơn do đã cắt giảm số lượng phần tử bỏ vào priority_queue nhờ bước chạy trước một cạnh Dijkstra. Và bước kiểm tra ~root~ có trùng không có thể được break sớm. Cho nên nhìn chung là thuật toán vẫn chạy đủ nhanh.

    Theo mình nộp thử thì thuật này chạy nhanh hơn thuật ở lời giải 1, chạy khoảng ~0,5s~.

    Code mẫu

    ideone

    Lời cuối cùng thì: mình xin chúc có bạn một mùa Tết ấm êm bên gia đình và bạn bè nhé!


  • 2
    TranThienPhuc2657  đã bình luận lúc 13, Tháng 2, 2026, 6:21 ← chỉnh sửa

    Về đề bài:

    • Quãng đường ~2R~ dặm không có nghĩa là đi được khoảng cách là ~2R~, như đề bài đã làm rõ ở trên. Mình thấy dữ kiện này bị thừa và gây nhiễu trong quá trình đọc đề, các bạn nên đọc kĩ để tránh hiểu nhầm ở đây.
    • Giả sử nếu mà đi từ trạm sạc này qua trạm sạc khác thì xe sẽ không được sạc đầy khi mà tới trạm sạc mới mà thay vào đó vẫn đi tiếp. Xe chỉ được sạc khi mà ở trạm sạc gốc, lúc mà mới bắt đầu đi và được sạc ~1~ lần duy nhất ở đó.