Năm 3742 đã đến, và bây giờ đến lượt Cyberland đăng cai APIO. Trong thế giới này có \(N\) quốc gia, được đánh số từ \(0\) đến \(N-1\), cùng với \(M\) con đường hai chiều, được đánh số từ \(0\) đến \(M-1\). Con đường thứ \(i\) (\(0\le i<M\)) nối hai quốc gia khác nhau \(x[i]\) và \(y[i]\), và cần \(c[i]\) đơn vị thời gian để đi hết con đường.

Tất cả thí sinh dự APIO đã đến Cyberland, ngoại trừ người đến từ quốc gia của bạn. Bạn sống ở quốc gia \(0\), còn Cyberland là quốc gia \(H\). Là người thông minh nhất đất nước, bạn được giao nhiệm vụ xác định thời gian nhỏ nhất để đi từ quốc gia của mình đến Cyberland.

Một số quốc gia có khả năng đặc biệt đưa tổng thời gian bạn đã đi về \(0\). Một số quốc gia khác có khả năng đặc biệt chia đôi tổng thời gian bạn đã đi (divide-by-2). Bạn có thể ghé thăm một quốc gia nhiều lần. Mỗi lần đến một quốc gia, bạn có thể chọn có sử dụng khả năng đặc biệt tại đó hay không, nhưng chỉ được sử dụng khả năng ấy nhiều nhất một lần trong lần ghé thăm đó. Vì vậy, nếu ghé thăm một quốc gia nhiều lần, bạn có thể dùng khả năng của quốc gia ấy nhiều lần.

Để tránh bị Tổ chức Hóa học Cyberland bắt, trong toàn bộ hành trình bạn chỉ được dùng khả năng divide-by-2 nhiều nhất \(K\) lần. Ngay khi đến Cyberland, bạn không được tiếp tục di chuyển vì kỳ thi APIO sắp bắt đầu.

Cho mảng arr có độ dài \(N\), trong đó \(arr[i]\) (\(0\le i<N\)) mô tả khả năng đặc biệt của quốc gia \(i\):

• \(arr[i]=0\): đưa tổng thời gian đã đi về \(0\);
• \(arr[i]=1\): giữ nguyên tổng thời gian đã đi;
• \(arr[i]=2\): chia đôi tổng thời gian đã đi.

Luôn có \(arr[0]=arr[H]=1\); nói cách khác, quốc gia của bạn và Cyberland không có khả năng đặc biệt.

Hãy tìm thời gian nhỏ nhất để đến Cyberland. Nếu không thể đến Cyberland, kết quả phải là \(-1\).

Yêu cầu cài đặt

Bạn cần cài đặt hàm sau:

double solve(int N, int M, int K, int H,
             std::vector<int> x, std::vector<int> y,
             std::vector<int> c, std::vector<int> arr);

• N: số quốc gia.
• M: số con đường hai chiều.
• K: số lần tối đa được sử dụng khả năng divide-by-2.
• H: chỉ số của quốc gia Cyberland.
• x, y, c: ba mảng độ dài \(M\); bộ ba \((x[i],y[i],c[i])\) biểu diễn con đường vô hướng thứ \(i\), nối \(x[i]\) với \(y[i]\) và có thời gian di chuyển \(c[i]\).
• arr: mảng độ dài \(N\); arr[i] mô tả khả năng đặc biệt của quốc gia \(i\).
• Hàm phải trả về thời gian nhỏ nhất để đi từ quốc gia \(0\) đến Cyberland nếu có thể đến đó, và trả về \(-1\) nếu không thể.
• Hàm có thể được gọi nhiều hơn một lần.

Giả sử giá trị do thí sinh trả về là \(ans_1\) và đáp án chính xác là \(ans_2\). Kết quả được coi là đúng khi và chỉ khi

Do hàm có thể được gọi nhiều lần, bạn phải bảo đảm dữ liệu còn lại từ một lần gọi trước không ảnh hưởng đến lần gọi hiện tại.

Submission phải sử dụng khai báo trong cyberland.h, chỉ cài đặt hàm trên và không tự cài đặt main hay đọc/ghi trực tiếp qua standard input/output.

Ví dụ

solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});

solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});

Ràng buộc

• \(2\le N\le10^5\), và tổng \(N\) qua mọi lần gọi không vượt quá \(10^5\).
• \(0\le M\le\min\left\{10^5,\frac{N(N-1)}2\right\}\), và tổng \(M\) qua mọi lần gọi không vượt quá \(10^5\).
• \(1\le K\le10^6\).
• \(1\le H<N\).
• \(0\le x[i],y[i]<N\) và \(x[i]\ne y[i]\).
• \(1\le c[i]\le10^9\).
• \(arr[i]\in\{0,1,2\}\).
• Mỗi cặp quốc gia được nối với nhau bởi nhiều nhất một con đường.

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo khuôn dạng sau:

• Dòng đầu chứa \(T\).
• Với mỗi trường hợp thử:
  • dòng đầu chứa \(N\), \(M\), \(K\);
  • dòng tiếp theo chứa \(H\);
  • dòng tiếp theo chứa \(arr[0],arr[1],\ldots,arr[N-1]\);
  • với mỗi \(i\) từ \(0\) đến \(M-1\), dòng tiếp theo chứa \(x[i]\), \(y[i]\), \(c[i]\).

Với mỗi trường hợp thử, trình chấm mẫu in trên một dòng giá trị mà hàm solve trả về.

Phần này chỉ mô tả giao diện của trình chấm mẫu; submission vẫn phải cài đặt hàm solve như ở trên.

Nguồn

Kho đề và dữ liệu chính thức APIO 2023, bài Cyberland. Gói nguồn được phát hành theo giấy phép CC0 1.0.