Đã đến lúc cho vòng chung kết Google Code Jam, và tất cả chúng ta đều muốn có mặt ở đó! Thật không may, một vài người trong chúng ta đã vô tình đến Mountain View thay vì địa điểm chính xác: London, Anh. Nhưng đừng lo lắng - chúng ta có thể bắt dịch vụ xe buýt đưa đón miễn phí của Google từ Mountain View đến London!

Dịch vụ xe buýt bao gồm \(M\) tuyến đường một chiều kết nối các cặp thành phố. Đối với mỗi tuyến đường, bạn biết nó đi từ thành phố nào đến thành phố nào, nhưng không may là bạn không biết chính xác các tuyến đường này dài bao nhiêu. Thay vào đó, với mỗi tuyến đường, bạn chỉ biết rằng độ dài của nó có thể là bất kỳ giá trị nguyên nào từ \(a_i\) đến \(b_i\), bao gồm cả hai đầu mút.

Tôi đã đi xe buýt của Google nhiều lần trước đây, vì vậy tôi đã đề xuất một lộ trình gồm các tuyến đường từ Mountain View đến London. Nhưng bạn lo lắng rằng kỹ năng tìm đường của tôi không tốt bằng bạn, và bạn muốn kiểm tra lại.

Cho lộ trình mà tôi đang đề xuất, liệu nó có thể là một con đường ngắn nhất từ Mountain View đến London không? Nếu không, ID của tuyến xe buýt đầu tiên trong lộ trình của tôi mà chắc chắn không nằm trong bất kỳ con đường ngắn nhất nào là gì (giả sử rằng tất cả các tuyến xe buýt trước đó đã được đi theo lộ trình tôi đề xuất)?

Ví dụ, giả sử chúng ta có danh sách các tuyến xe buýt sau:

ID | Start City     |  Destination City  |  Shuttle Length
---+----------------+--------------------+----------------
1  | Mountain View  |  London            |  [100, 1000]
2  | Mountain View  |  Paris             |  [500, 5000]
3  | Paris          |  London            |  [400, 600]
4  | Paris          |  Moscow            |  [500, 5000]
5  | Moscow         |  London            |  [1, 10000]

Tôi đề xuất lộ trình Mountain View -> Paris -> Moscow -> London. Con đường ngắn nhất thực sự có thể là tuyến đường trực tiếp từ Mountain View đến London, hoặc lộ trình Mountain View -> Paris -> London. Điều này có nghĩa là tuyến đường thứ hai trong lộ trình của tôi (Paris -> Moscow) là tuyến đường đầu tiên chắc chắn không phải là một phần của con đường ngắn nhất.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên dương \(N\), \(M\) và \(P\). \(N\) đại diện cho tổng số thành phố (các thành phố được đánh số từ \(1\) đến \(N\)), \(M\) đại diện cho tổng số tuyến xe buýt, và \(P\) đại diện cho số lượng tuyến xe buýt trong lộ trình của tôi từ Mountain View (thành phố số 1) đến London (thành phố số 2).

Tiếp theo là \(M\) dòng, mỗi dòng gồm bốn số nguyên \(u_i, v_i, a_i, b_i\). Mỗi dòng thể hiện rằng có một tuyến xe buýt một chiều từ thành phố \(u_i\) đến thành phố \(v_i\), và bạn biết rằng độ dài của nó có thể là bất kỳ giá trị nguyên nào từ \(a_i\) đến \(b_i\). Các tuyến đường được cấp ID từ \(1\) đến \(M\) theo đúng thứ tự trong dữ liệu vào.

Tiếp theo là một dòng gồm \(P\) số nguyên duy nhất trong phạm vi từ \(1\) đến \(M\). Những số này đại diện cho các tuyến xe buýt tôi đang đưa bạn đi, theo đúng thứ tự. Mỗi số là ID của một tuyến đường từ danh sách trước đó.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: n", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và n là ID của tuyến xe buýt đầu tiên trong lộ trình của tôi mà không thể là một phần của con đường ngắn nhất từ Mountain View đến London. Nếu không có tuyến đường nào như vậy, hãy in "Looks Good To Me".

Ràng buộc

• \(1 \le T \le 10\).
• \(1 \le u_i, v_i \le N\).
• \(1 \le a_i \le b_i \le 1,000,000\).
• Lộ trình của tôi được đảm bảo là một lộ trình hợp lệ từ Mountain View (thành phố số 1) đến London (thành phố số 2).
• Có thể có nhiều hơn một tuyến xe buýt giữa cùng hai thành phố và có thể có tuyến xe buýt đi từ một thành phố đến chính nó. Ngoài ra, lộ trình được đề xuất có thể đi qua cùng một thành phố nhiều lần, nhưng nó sẽ không sử dụng cùng một tuyến xe buýt nhiều lần.

Phân nhóm

• Small dataset: \(2 \le N \le 20, 1 \le M \le 20, 1 \le P \le 10\).
• Large dataset: \(2 \le N \le 1000, 1 \le M \le 2000, 1 \le P \le 500\).

Đ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
4 5 3
1 2 100 1000
1 3 500 5000
3 2 400 600
3 4 500 5000
4 2 1 10000
2 4 5
3 3 2
1 3 1 1
3 2 1 1
1 2 1 2
1 2
5 6 3
1 3 1 1
4 2 1 9
1 4 1 1
3 5 2 2
5 2 2 2
3 4 1 2
1 6 2

Case #1: 4
Case #2: Looks Good To Me
Case #3: 6

Nguồn

Google Code Jam 2013, Vòng 3, bài Are We Lost Yet?.

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