Năm 1860, Pony Express là hệ thống chuyển thư nhanh nhất nối bờ Đông và bờ Tây Hoa Kỳ. Hệ thống phục vụ \(N\) thành phố. Mỗi thành phố có đúng một con ngựa; mỗi con đi với một tốc độ không đổi nhất định và có tổng quãng đường tối đa mà nó có thể đi trước khi quá mệt để tiếp tục.

Người đưa thư Pony Express khởi hành bằng ngựa của thành phố xuất phát. Mỗi khi tới một thành phố, người đó có thể tiếp tục dùng con ngựa hiện tại hoặc đổi sang ngựa của thành phố ấy; việc đổi ngựa diễn ra tức thời. Ngựa không bao giờ có cơ hội nghỉ, nên một phần sức bền tối đa đã dùng thì mất vĩnh viễn. Khi người đưa thư tới thành phố đích, thư được giao.

Các tuyến giữa thành phố được thiết lập qua những cuộc thương lượng phức tạp giữa chủ công ty, nhà lập pháp, đại diện công đoàn và ông anh họ Pete. Vì vậy khoảng cách không nhất thiết tuân theo lẽ thường: chúng không nhất thiết thỏa bất đẳng thức tam giác, và khoảng cách từ A đến B có thể khác khoảng cách từ B đến A.

Bạn là một doanh nhân du hành thời gian và mang theo một máy tính nhanh từ tương lai. Một máy tính chưa đủ để lập dịch vụ thư điện tử khiến Pony Express lỗi thời, nhưng có thể dùng nó để lập tuyến tối ưu. Với toàn bộ dữ liệu về đường đi, ngựa ở từng thành phố và danh sách các cặp thành phố đầu-cuối, hãy tính nhanh thời gian tối thiểu cho mỗi chuyến giao thư. Mọi chuyến giao thư được xem là độc lập; dùng thành phố hay ngựa trong một chuyến không làm chúng mất đi ở chuyến khác.

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test gồm:

• Một dòng chứa \(N\), số thành phố có ngựa, và \(Q\), số cặp điểm dừng cần xét. Các thành phố được đánh số từ 1 đến \(N\).
• \(N\) dòng, dòng thứ \(i\) chứa \(E_i\), tổng quãng đường tối đa (km) ngựa ở thành phố \(i\) có thể đi, và \(S_i\), tốc độ không đổi (km/h) của nó.
• \(N\) dòng, mỗi dòng \(N\) số nguyên. Số thứ \(j\) trên dòng thứ \(i\), \(D_{ij}\), bằng -1 nếu không có tuyến trực tiếp từ thành phố \(i\) đến \(j\), và bằng độ dài tuyến đó (km) nếu có.
• \(Q\) dòng, dòng thứ \(k\) chứa \(U_k,V_k\), lần lượt là điểm xuất phát và điểm đến của cặp thành phố thứ \(k\) cần xét.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y1 y2 ... yQ, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn \(y_k\) là thời gian tối thiểu theo giờ để giao thư từ \(U_k\) đến \(V_k\).

Mỗi \(y_k\) được coi là đúng nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\); \(2\le N\le100\).
• \(1\le E_i\le10^9\) và \(1\le S_i\le1000\) với mọi \(i\).
• \(-1\le D_{ij}\le10^9\); \(D_{ii}=-1\); \(D_{ij}\ne0\) với mọi \(i,j\).
• \(U_k\ne V_k\) với mọi \(k\).
• Mọi chuyến từ \(U_k\) đến \(V_k\) đều được bảo đảm thực hiện được bằng các con ngựa đã cho.
• Không cặp có thứ tự nào bị lặp trong cùng một bộ test: với mọi \(l\ne m\), \(U_l\ne U_m\) và/hoặc \(V_l\ne V_m\).

Phân nhóm

• Test Set 1 (Visible): \(D_{ij}=-1\) với mọi \(i,j\) mà \(i+1\ne j\); các thành phố nằm trên một đường thẳng và mỗi tuyến chỉ đi từ một thành phố tới thành phố kế tiếp. \(Q=1\), \(U_1=1\), \(V_1=N\); chỉ cần tính chuyến từ thành phố đầu đến thành phố cuối.
• Test Set 2 (Hidden): \(1\le Q\le100\); \(1\le U_k,V_k\le N\) với mọi \(k\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
3 1
2 3
2 4
4 4
-1 1 -1
-1 -1 1
-1 -1 -1
1 3
4 1
13 10
1 1000
10 8
5 5
-1 1 -1 -1
-1 -1 1 -1
-1 -1 -1 10
-1 -1 -1 -1
1 4
4 3
30 60
10 1000
12 5
20 1
-1 10 -1 31
10 -1 10 -1
-1 -1 -1 10
15 6 -1 -1
2 4
3 1
3 2

Case #1: 0.583333333
Case #2: 1.2
Case #3: 0.51 8.01 8.0

Nguồn

Google Code Jam 2017, Vòng 1B, bài Pony Express.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.