Nước JOI có \(N\) thành phố, đánh số từ \(0\) đến \(N-1\). Có \(A\) tuyến đường sắt, đánh số từ \(0\) đến \(A-1\). Tuyến thứ \(i\) nối hai chiều giữa \(U_i\) và \(V_i\), với giá vé \(C_i\). Các tuyến đường sắt nối các cặp thành phố khác nhau.

Cũng có \(B\) tuyến xe buýt, đánh số từ \(0\) đến \(B-1\). Tuyến thứ \(j\) nối hai chiều giữa \(S_j\) và \(T_j\), với giá vé \(D_j\). Các tuyến xe buýt nối các cặp thành phố khác nhau. Một tuyến đường sắt và một tuyến xe buýt có thể nối cùng một cặp thành phố. Có thể đi giữa bất kỳ hai thành phố nào bằng đường sắt và/hoặc xe buýt.

Azer muốn biết tổng giá vé nhỏ nhất để đi từ thành phố \(0\) đến từng thành phố. Azer chỉ biết các tuyến đường sắt, còn Baijan chỉ biết các tuyến xe buýt. Hai người trao đổi các ký tự 0 hoặc 1, với tổng số ký tự cả hai gửi không quá \(58\,000\).

Hãy cài đặt chương trình cho cả Azer và Baijan để sau khi trao đổi, Azer tìm được các giá trị cần thiết.

Giao diện tương tác

Nộp một tệp C++ cài đặt cả hai phần Azer và Baijan, khai báo #include "transportations.h". Không cài đặt hàm main. Phần Azer gồm các hàm:

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C);
void ReceiveA(bool x);
std::vector<int> Answer();

• InitA được gọi đúng một lần lúc bắt đầu. \(N\) là số thành phố, \(A\) là số tuyến đường sắt. Các mảng U, V, C có độ dài \(A\), mô tả hai đầu mút và giá vé của từng tuyến.
• ReceiveA(x) được gọi mỗi khi Azer nhận một ký tự từ Baijan; true biểu diễn 1, false biểu diễn 0.
• Answer() được gọi đúng một lần khi tất cả ký tự đã được nhận. Hàm phải trả về mảng Z có độ dài \(N\), nếu không nhận Wrong Answer [1]. Z[k] phải là tổng giá vé nhỏ nhất từ thành phố \(0\) đến thành phố \(k\); đặc biệt Z[0] = 0.

Trong phần Azer, có thể gọi hàm do thư viện cung cấp để gửi một ký tự cho Baijan:

void SendA(bool y);

Trong cùng tệp nộp, cài đặt phần Baijan gồm các hàm:

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D);
void ReceiveB(bool y);

• InitB được gọi đúng một lần lúc bắt đầu. \(N\) là số thành phố, \(B\) là số tuyến xe buýt. Các mảng S, T, D có độ dài \(B\), mô tả hai đầu mút và giá vé của từng tuyến.
• ReceiveB(y) được gọi mỗi khi Baijan nhận một ký tự từ Azer; true biểu diễn 1, false biểu diễn 0.

Trong phần Baijan, có thể gọi hàm do thư viện cung cấp để gửi một ký tự cho Azer:

void SendB(bool x);

Thứ tự trao đổi

Với mỗi test, trình chấm tạo hai hàng đợi: \(Q_Y\) chứa các ký tự Azer gửi và \(Q_X\) chứa các ký tự Baijan gửi. Trước tiên, gọi InitA, rồi InitB; các ký tự gửi trong hai hàm này được đưa vào hàng đợi tương ứng.

• Nếu ít nhất một hàng đợi không rỗng, lấy một ký tự ở đầu hàng đợi đó và gọi ReceiveA hoặc ReceiveB tương ứng. Nếu cả hai hàng đợi đều không rỗng, không quy định bên nào được nhận trước.
• Khi SendA được gọi trong ReceiveA, ký tự gửi được đưa vào \(Q_Y\).
• Khi SendB được gọi trong ReceiveB, ký tự gửi được đưa vào \(Q_X\).
• Khi cả hai hàng đợi đều rỗng, gọi Answer rồi kết thúc chương trình.

Tổng số lần gọi SendA và SendB không được vượt quá \(58\,000\), nếu không nhận Wrong Answer [2].

Có thể khai báo biến toàn cục và hàm phụ. Tệp nộp được biên dịch cùng trình chấm thành một tệp thực thi. Nên đặt biến và hàm phụ của hai bên trong các namespace khác nhau để tránh trùng tên, còn các hàm giao diện ở trên phải được khai báo ở phạm vi toàn cục. Đặt các chỉ thị #include ngoài namespace. Khi chấm thực tế, cùng tệp thực thi được chạy thành hai tiến trình riêng cho Azer và Baijan, không chia sẻ biến toàn cục. Tiến trình Azer chỉ nhận dữ liệu đường sắt và được gọi các hàm của Azer; tiến trình Baijan chỉ nhận dữ liệu xe buýt và được gọi các hàm của Baijan.

Không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Thư viện thử nghiệm

Gói tệp mẫu chứa transportations.h, transportations.cpp, grader.cpp và README.txt. Tệp README.txt giải thích cách chuyển từ giao diện hai tệp của đề gốc sang giao diện một tệp nộp. Đặt ba tệp mã nguồn và tiêu đề trong cùng thư mục, thay nội dung transportations.cpp bằng lời giải của bạn và biên dịch bằng:

g++ -std=gnu++14 -O2 -o grader grader.cpp transportations.cpp

Trình chấm mẫu chạy trong một tiến trình, khác với trình chấm thực tế.

Dữ liệu vào

Đầu vào của trình chấm mẫu có dạng:

N A B
U_0 V_0 C_0
...
U_{A-1} V_{A-1} C_{A-1}
S_0 T_0 D_0
...
S_{B-1} T_{B-1} D_{B-1}

Nếu \(A=0\) hoặc \(B=0\), phần tương ứng không có dòng nào.

Dữ liệu ra

Theo mô tả trong đề chính thức, trình chấm mẫu ghi loại lỗi Wrong Answer [1] hoặc Wrong Answer [2] ra đầu ra lỗi chuẩn và không ghi gì ra đầu ra chuẩn nếu có lỗi. Nếu không, nó ghi Accepted: L ra đầu ra lỗi chuẩn, trong đó \(L\) là tổng số ký tự đã gửi, và ghi mảng trả về ra đầu ra chuẩn, mỗi phần tử một dòng:

Z[0]
...
Z[N-1]

Trình chấm mẫu không kiểm tra các giá trị trong Z có đúng hay không. Nếu có nhiều loại lỗi, chỉ một loại được báo.

Ràng buộc

• \(1\le N\le2000\).
• \(0\le A,B\le500\,000\).
• \(0\le U_i,V_i\le N-1\) và \(U_i\ne V_i\) với \(0\le i<A\).
• Hai tuyến đường sắt khác nhau không nối cùng một cặp thành phố, kể cả khi đảo thứ tự hai đầu mút.
• \(0\le S_j,T_j\le N-1\) và \(S_j\ne T_j\) với \(0\le j<B\).
• Hai tuyến xe buýt khác nhau không nối cùng một cặp thành phố, kể cả khi đảo thứ tự hai đầu mút.
• Có thể đi giữa mọi cặp thành phố bằng đường sắt và/hoặc xe buýt.
• \(1\le C_i\le500\) với \(0\le i<A\).
• \(1\le D_j\le500\) với \(0\le j<B\).

Phân nhóm

1. (6 điểm) \(A=0\).
2. (8 điểm) \(B\le1000\).
3. (8 điểm) \(A+B=N-1\).
4. (38 điểm) \(N\le900\).
5. (14 điểm) \(N\le1100\).
6. (10 điểm) \(N\le1400\).
7. (16 điểm) Không có ràng buộc bổ sung.

Ví dụ giao tiếp

4 3 4
0 1 6
2 1 4
2 0 10
1 2 3
3 1 1
3 2 3
3 0 7

Một chuỗi lời gọi tương ứng:

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 2. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.