JOI 2024 - Highway Tolls

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2100 (p) Thời gian: 4.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Vương quốc JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\). Có \(M\) đường cao tốc một chiều nối các thành phố, được đánh số từ \(1\) đến \(M\). Đi qua đường cao tốc \(i\) (\(1 \le i \le M\)) cho phép di chuyển từ thành phố \(A_i\) đến thành phố \(B_i\) và mất \(L_i\) đơn vị thời gian.

Mỗi lần đi qua một đường cao tốc, bạn phải trả phí. Phí thấp nhất của đường cao tốc \(i\) là \(C_i\). Tuy nhiên, mọi người lao động ở vương quốc JOI đều không thích làm việc ngoài giờ, nên càng cách xa thời điểm chuẩn \(0\), phí càng tăng. Cụ thể, nếu rời thành phố \(A_i\) vào thời điểm \(t\) để đi qua đường cao tốc \(i\), bạn phải trả phí \(C_i + K \times |t|\), trong đó \(K\) là một hằng số và \(|t|\) là giá trị tuyệt đối của \(t\).

Bạn sống ở thành phố \(1\) và muốn đến thăm người bạn sống ở thành phố \(N\). Trước hết, bạn muốn biết có thể đi từ thành phố \(1\) đến thành phố \(N\) bằng các đường cao tốc hay không. Nếu có, bạn muốn tìm tổng phí ít nhất phải trả. Bạn được tự do chọn lộ trình và thời điểm rời mỗi thành phố. Đặc biệt, bạn có thể rời thành phố \(1\) tại một thời điểm âm, hoặc ở lại một thành phố trong một khoảng thời gian mà không đi qua đường cao tốc nào.

Cho thông tin về các đường cao tốc và hằng số \(K\), hãy viết chương trình xác định có thể đi từ thành phố \(1\) đến thành phố \(N\) hay không và, nếu có, tìm tổng phí ít nhất phải trả.

Có thể chứng minh rằng, với các ràng buộc của bài toán, nếu tồn tại cách di chuyển thì tổng phí nhỏ nhất luôn là một số nguyên.

Dữ liệu vào

Dòng thứ nhất chứa ba số nguyên \(N, M, K\).

Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(A_i, B_i, L_i, C_i\), cách nhau bởi dấu cách.

Dữ liệu ra

Nếu không thể đi từ thành phố \(1\) đến thành phố \(N\) bằng các đường cao tốc, in ra -1. Ngược lại, in ra trên một dòng số nguyên biểu diễn tổng phí ít nhất phải trả.

Ràng buộc

  • \(2 \le N \le 4000\).
  • \(1 \le M \le 8000\).
  • \(0 \le K \le 100\,000\).
  • \(1 \le A_i \le N\) với mọi \(1 \le i \le M\).
  • \(1 \le B_i \le N\) với mọi \(1 \le i \le M\).
  • \(A_i \ne B_i\) với mọi \(1 \le i \le M\).
  • \(1 \le L_i \le 1\,000\,000\) với mọi \(1 \le i \le M\).
  • \(0 \le C_i \le 10^9\) với mọi \(1 \le i \le M\).
  • Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

  1. (9 điểm) \(N \le 100\), \(M \le 200\), \(K = 0\).
  2. (21 điểm) \(N \le 100\), \(M \le 200\), \(L_i \le 20\) với mọi \(1 \le i \le M\).
  3. (13 điểm) \(N \le 100\), \(M=N-1\), \(A_i=i\) và \(B_i=i+1\) với mọi \(1 \le i \le M\).
  4. (23 điểm) \(N \le 100\), \(M \le 200\), \(N\) là số chẵn và \(\lfloor B_i/2 \rfloor - \lfloor A_i/2 \rfloor = 1\) với mọi \(1 \le i \le M\). Ở đây, \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\).
  5. (16 điểm) \(N \le 100\), \(M \le 200\).
  6. (11 điểm) \(N \le 1500\), \(M \le 3000\).
  7. (7 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
4 4 2
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3
Output 
15
Giải thích

Các thành phố và đường cao tốc được biểu diễn như hình dưới đây. Mỗi hình tròn là một thành phố, số bên trong là số hiệu thành phố; mỗi mũi tên là một đường cao tốc. Hai số ghi cạnh mỗi đường lần lượt là \(L_i\) và \(C_i\).

Có thể di chuyển như sau để tổng phí bằng \(15\):

  • Thời điểm \(-1\): rời thành phố \(1\) để đến thành phố \(3\). Phí là \(10 + 2 \times |-1| = 12\).
  • Thời điểm \(0\): đến thành phố \(3\) và lập tức đi tiếp đến thành phố \(4\). Phí là \(3 + 2 \times |0| = 3\).
  • Thời điểm \(5\): đến thành phố \(4\).

Không có cách di chuyển nào có tổng phí nhỏ hơn \(15\), nên in ra \(15\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 5, 6, 7\).

Ví dụ 2

Input 
4 4 0
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3
Output 
9
Giải thích

Ví dụ này chỉ khác ví dụ \(1\) ở giá trị của \(K\). Có thể di chuyển như sau để tổng phí bằng \(9\):

  • Thời điểm \(-3\): rời thành phố \(1\) để đến thành phố \(2\). Phí là \(2 + 0 \times |-3| = 2\).
  • Thời điểm \(0\): đến thành phố \(2\) và lập tức đi tiếp đến thành phố \(3\). Phí là \(4 + 0 \times |0| = 4\).
  • Thời điểm \(1\): đến thành phố \(3\) và ở lại đó.
  • Thời điểm \(3\): rời thành phố \(3\) để đến thành phố \(4\). Phí là \(3 + 0 \times |3| = 3\).
  • Thời điểm \(8\): đến thành phố \(4\).

Không có cách di chuyển nào có tổng phí nhỏ hơn \(9\), nên in ra \(9\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 5, 6, 7\).

Ví dụ 3

Input 
2 1 10
2 1 4 7
Output 
-1
Giải thích

Không thể đi từ thành phố \(1\) đến thành phố \(2\) bằng đường cao tốc, nên in ra -1.

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 5, 6, 7\).

Ví dụ 4

Input 
4 3 5
1 2 3 1
2 3 1 10
3 4 7 6
Output 
37
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3, 5, 6, 7\).

Ví dụ 5

Input 
8 8 2
1 2 1 5
5 6 3 1
2 4 10 18
3 5 3 1
1 3 4 2
5 6 2 2
2 5 2 3
6 8 1 1
Output 
25
Giải thích

Có thể tồn tại nhiều đường cao tốc có cùng cặp đầu mút \((A_i,B_i)\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 4, 5, 6, 7\).

Ví dụ 6

Input 
6 10 100000
4 2 212037 752027141
2 5 667097 1571491
2 1 769275 576006950
1 2 711969 526189398
5 3 733555 206320177
3 4 364807 802102091
1 4 467240 183184247
3 5 44994 15991843
5 3 613192 782356546
4 6 832593 639529758
Output 
47546714005
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(5, 6, 7\).

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: