ROADS - Roads

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/roads


Có N thành phố 1..N nối bởi các con đường một chiều. Mỗi con đường có hai giá trị: độ dài và chi phí phải trả để đi qua. Bob ở thành phố 1. Bạn hãy giúp Bob tìm đường đi ngắn nhất đến thành phố N, biết rằng Bob chỉ có số tiền có hạn là K mà thôi.

Dữ liệu

Dòng đầu tiên ghi t là số test. Với mỗi test, dòng đầu ghi K (0 ≤ K ≤ 10000). Dòng 2 ghi N, 2 ≤ N ≤ 100. Dòng 3 ghi R, 1 ≤ R ≤ 10000 là số đường nối. Mỗi dòng trong N dòng sau ghi 4 số nguyên S, D, L, T mô tả một con đường nối giữa S và D với độ dài L ( 1 ≤ L ≤ 100) và chi phí T (0 ≤ T ≤ 100). Lưu ý có thể có nhiều con đường nối giữa hai thành phố.

Kết quả

Với mỗi test, in ra độ dài đường đi ngắn nhất từ 1 đến N mà tổng chi phí không quá K. Nếu không tồn tại, in ra -1.

Ví dụ

Dữ liệu
2
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
0
4
4
1 4 5 2
1 2 1 0
2 3 1 1
3 4 1 0

Kết quả
11
-1


Được gửi lên bởi:Jimmy
Ngày:2005-04-28
Thời gian chạy:7s
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:Central European Olympiad in Informatics 98

hide comments
2015-12-01 08:55:49 Lê Nguyên Khôi
Tồn tại 1 thằng nói bậy ở dưới
2015-07-31 19:11:23 Ndkhaivn
Tồn tại ít nhất 1 thằng ở dưới nói láo
2015-07-30 05:20:49 Lê Quang Vũ
Thằng ở dưới nói láo .
2015-07-30 05:16:13 Lê Hoàng Vũ
Đệ Quy với Ma Trận Kề :v
Chục Phát AC
2015-07-24 18:43:52 never give up !!
DFS rồi :)))) [nongdanjohn]
2015-07-10 06:00:07 _sanghk11_
e lm dijkstra đc ko mn ????? :v

Last edit: 2015-07-10 06:15:21
2015-06-26 14:01:52 Prismatic
dfs 1 hit AC :)
2015-05-25 06:14:37 Chuyên Nhật CNN
bài này cách chuẩn là gì ai chỉ cho mình đc ko ? .-. mình dùng bellman ford
2014-12-24 09:40:53 FO3 Ronaldinho Gaucho XI !!!!
Đề Sai :v :v
Mỗi dòng trong """"N"""" dòng sau ghi 4 số nguyên S, D, L, T mô tả một con đường nối giữa S và D với độ dài L ( 1 ≤ L ≤ 100) và chi phí T (0 ≤ T ≤ 100).
2014-11-12 07:48:01 [ND] HI
cẩn thận nhá, ĐƯỜNG MỘT CHIỀU !!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.