trang chủ / đề bài / icpc23_mt_f

Trà sữa

Đề bài

Mô tả

Suika là một fan cuồng của trà sữa Đài Loan, ngày nào cô bé cũng có thể uống một cốc lớn, có hôm còn uống hai cốc. Sau năm học vừa qua, Suika được trao danh hiệu học sinh có thành tích cao nhất toàn trường. Để chúc mừng thành tích này, bố mẹ quyết định tặng cô bé một chuyến du lịch Đài Loan để cô bé thoải mái thư giãn và chuẩn bị cho năm học mới.

Dĩ nhiên Suika định uống thật nhiều trà sữa khi ở Đài Loan. Chỉ thử vài cốc thì chưa đủ: sau một thời gian suy nghĩ, cô bé nói với bố mẹ rằng mình sẽ uống trà sữa ở mọi thị trấn mình đi qua. Cô bé cũng có một kế hoạch rất rõ ràng về các thị trấn sẽ ghé thăm. Nhưng Suika vẫn chỉ là một cô bé, và đây là lần đầu cô bé đi nước ngoài mà không có bố mẹ, nên Suika chỉ ghi nhớ một danh sách ngắn nhất các con đường để đi lại giữa các thị trấn đó. Giả sử có N thị trấn cô bé muốn ghé thăm, cho đơn giản cô bé chỉ biết N−1 con đường hai chiều (các con đường này nối tất cả các thị trấn với nhau). Cô bé đánh số các thị trấn từ 1 tới N và quyết định ghé thăm chúng theo thứ tự từ 1 tới N. Nghĩa là cô bé sẽ đến thị trấn 1 và uống một cốc trà sữa, đi tham quan, rồi đến thị trấn 2 và lại uống trà sữa, cứ thế tiếp tục.

Để đi qua một tuyến đường cụ thể, cô bé cần có vé tàu hợp lệ. Với tuyến tàu thứ i có 2 loại vé: vé một lượt có giá Ci1 đô la Đài Loan và vé nhiều lượt có giá Ci2 đô la. Với mỗi tuyến, cô bé có thể chọn mua một vé một lượt mỗi lần cần đi qua tuyến đó, hoặc mua một vé nhiều lượt duy nhất một lần.

Hãy giúp Suika tìm số đô la Đài Loan nhỏ nhất cô bé cần chi để tận hưởng trọn vẹn chuyến đi.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên N (2≤N≤105).
  • N−1 dòng tiếp theo, mỗi dòng chứa 4 số nguyên Ai,Bi,Ci1,Ci2 (1≤Ai,Bi≤N, 1≤Ci1,Ci2≤100000): thị trấn Ai và Bi được nối bởi một tuyến tàu với giá vé một lượt Ci1 và giá vé nhiều lượt Ci2.

Dữ liệu ra

In ra một dòng duy nhất là chi phí nhỏ nhất cho chuyến đi.

Ràng buộc

  • 2≤N≤105
  • 1≤Ai,Bi≤N
  • 1≤Ci1,Ci2≤100000
  • N−1 tuyến tàu nối tất cả các thị trấn với nhau.

Ví dụ

Input Output Giải thích
5
1 2 1 3
1 3 1 4
2 4 2 3
3 5 2 3
11 Suika đi qua 4 tuyến lần lượt 4,3,2,1 lần. Cô bé mua vé nhiều lượt cho tuyến 1 và 3, vé một lượt cho tuyến 2 và 4. Chi phí: 3+3×1+3+1×2=11.
5
1 2 3 5
1 3 2 3
1 4 1 3
1 5 2 3
12 Các tuyến được đi qua lần lượt 2,2,2,1 lần. Chi phí: 5+3+2×1+1×2=12.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0