Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBROBOT - VOI07 Robot cứu hỏa

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbrobot


Trên một mạng lưới giao thông có n nút, các nút được đánh số từ 1 đến n và giữa hai nút bất kỳ có không quá một đường nối trực tiếp (đường nối trực tiếp là một đường hai chiều). Ta gọi đường đi từ nút s đến nút t là một dãy các nút và các đường nối trực tiếp có dạng:

s = u1, e1, u2,..., ui, ei, ui+1, ..., uk-1, ek-1, uk = t,

trong đó u1, u2, …, uk là các nút trong mạng lưới giao thông, ei là đường nối trực tiếp giữa nút ui và ui+1 (không có nút uj nào xuất hiện nhiều hơn một lần trong dãy trên, j = 1, 2, …, k).

Biết rằng mạng lưới giao thông được xét luôn có ít nhất một đường đi từ nút 1 đến nút n.

Một robot chứa đầy bình với w đơn vị năng lượng, cần đi từ trạm cứu hoả đặt tại nút 1 đến nơi xảy ra hoả hoạn ở nút n, trong thời gian ít nhất có thể. Thời gian và chi phí năng lượng để robot đi trên đường nối trực tiếp từ nút i đến nút j tương ứng là tij và cij (1 ≤ i, j ≤ n). Robot chỉ có thể đi được trên đường nối trực tiếp từ nút i đến nút j nếu năng lượng còn lại trong bình chứa không ít hơn cij (1 ≤ i, j ≤ n). Nếu robot đi đến một nút có trạm tiếp năng lượng (một nút có thể có hoặc không có trạm tiếp năng lượng) thì nó tự động được nạp đầy năng lượng vào bình chứa với thời gian nạp coi như không đáng kể.

Yêu cầu: Hãy xác định giá trị w nhỏ nhất để robot đi được trên một đường đi từ nút 1 đến nút n trong thời gian ít nhất.

Input

Dòng đầu tiên chứa một số nguyên dương n (2 ≤ n ≤ 500);

Dòng thứ hai chứa n số, trong đó số thứ j bằng 1 hoặc 0 tương ứng ở nút j có hoặc không có trạm tiếp năng lượng (j = 1, 2, …, n);

Dòng thứ ba chứa số nguyên dương m (m ≤ 30000) là số đường nối trực tiếp có trong mạng lưới giao thông;

Dòng thứ k trong số m dòng tiếp theo chứa 4 số nguyên dương i, j, tij, cij (tij, cij ≤ 10000) mô tả đường nối trực tiếp từ nút i đến nút j, thời gian và chi phí năng lượng tương ứng.

Hai số liên tiếp trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách.

Output

Ghi ra số nguyên dương w tìm được.

Example

Input:
4
0 1 1 0
5
1 2 5 4
1 3 4 3
1 4 9 4
2 4 4 1
3 4 5 2

Output:
3


Được gửi lên bởi:special_one
Ngày:2008-09-21
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Vietnam Olympiad of Informatics 2007

hide comments
2018-08-15 21:04:21
đề bài mập mờ thế. đi với năng lượng w ít nhất thì sao mà thời gian ít nhất dc? và ngược lại.
2018-07-29 04:34:10
Không đọc kĩ đó là đường 2 chiều đấm gãy tay mới xong :((
2018-06-27 11:00:28
Dm lâu nay quen cài Dijkstra heap bữa nay cài lại Dijk thường mất nhiều đấm quá -_*
#147
2017-11-28 15:21:28
chặt nhị phân + dijisktra => AC
2017-11-02 14:51:38
Fan hâm mộ chào Lê Tuấn Dũng
2017-08-22 10:52:35
kham khảo:
https://vietcodes.github.io/code/56/
2017-07-27 03:50:20
Code AC: http://shink.in/cMDCv
2017-05-28 05:26:10
Mấy bác được 94,12 thử test này nhé, đảm bảo mấy bác sai luôn, bởi còn trường hợp chưa xét:

5
0 1 1 0 0
5
1 2 5 4
1 3 4 3
1 4 9 4
2 4 4 1
3 4 5 2
4 5 7 3

kq đúng là 4, cứ vẽ ra rồi kiểm nghiệm, còn kq của chương trình các bác sẽ ra 5, đảm bảo luôn ^^
from Dinh Truong Lam
2016-12-08 04:38:17 le tuan dung
Tôi là Lê Tuấn Dũng. Xin chào các fan hâm mộ.
2016-07-15 04:32:02
DFS muôn năm
duyệt trâu muôn năm
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.