Vé Tham Quan

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie đang leo một con đường mòn có $N$ trạm kiểm tra, được đánh số từ $1$ đến $N$ . Có $K$ vé có thể mua. Vé thứ $i$ được bán tại trạm $c_{i}$ với giá $p_{i}$ và cho phép Bessie đi vào tất cả các trạm trong đoạn $[a_{i}, b_{i}]$ .

Trước khi bước vào bất kỳ trạm nào, Bessie phải đã mua ít nhất một vé cho phép đi vào trạm đó. Khi đã có quyền đi vào một trạm, cô có thể quay lại đó bất cứ lúc nào. Bessie có thể di chuyển tự do giữa các trạm mà cô có quyền đi vào.

Với mỗi trạm bắt đầu $i$ ( $1 \leq i \leq N$ ), hãy xác định chi phí tối thiểu để Bessie có thể đi đến được cả trạm $1$ và trạm $N$ , hoặc xuất $- 1$ nếu không thể.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ( $1 \leq N, K \leq 10^{5}$ ).
$K$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $c_{i}$ , $p_{i}$ , $a_{i}$ , $b_{i}$ ( $1 \leq c_{i}, a_{i}, b_{i} \leq N$ ; $1 \leq p_{i} \leq 10^{9}$ ), mô tả một vé được bán tại trạm $c_{i}$ với giá $p_{i}$ cho phép đi vào các trạm từ $a_{i}$ đến $b_{i}$ .

Dữ liệu ra

Gồm $N$ dòng, dòng thứ $i$ chứa chi phí tối thiểu để từ trạm $i$ có thể đi đến cả trạm $1$ và trạm $N$ , hoặc $- 1$ nếu không thể.

Ràng buộc

$1 \leq N, K \leq 10^{5}$
$1 \leq c_{i}, a_{i}, b_{i} \leq N$
$1 \leq p_{i} \leq 10^{9}$
Test 1-7: $N, K \leq 1000$
Test 8-19: Không có ràng buộc bổ sung

Ví dụ

Input	Output	Giải thích
7 6 4 1 2 3 4 10 5 6 2 100 7 7 6 1000 1 1 5 10000 1 4 6 100000 5 6	-1 -1 -1 1111 10100 110100 -1	Từ trạm $4$ : mua vé 1 (giá 1, phủ 2-3), vé 2 (giá 10, phủ 5-6), vé 4 (giá 1000, phủ 1), vé 6 (giá 100, phủ 5-6) rồi vé thêm để phủ hết. Chi phí tối thiểu là $1111$ . Từ trạm $1, 2, 3, 7$ không thể đi đến cả hai đầu.

Ghi chú

Bessie bắt đầu tại một trạm và cần mua các vé tại các trạm mà cô có quyền đi vào để mở rộng phạm vi. Mục tiêu là phủ được cả trạm $1$ và trạm $N$ với tổng chi phí nhỏ nhất.

Bình luận

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