Hành Trình Dài Nhất Nhỏ Nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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 đi du lịch qua xứ sở bò Cowland có $N$ thị trấn ( $2 \leq N \leq 2 \cdot 10^{5}$ ) được nối bằng $M$ con đường một chiều ( $1 \leq M \leq 4 \cdot 10^{5}$ ). Mỗi con đường có một nhãn (label) là số nguyên dương.

Một hành trình là dãy các thị trấn liên tiếp nối bằng đường. Độ dài hành trình là số con đường đi qua. Giá trị hành trình là tổng các nhãn trên đường đi. Đảm bảo không tồn tại hành trình vô hạn (đồ thị là DAG).

Với mỗi thị trấn xuất phát, Bessie muốn tìm hành trình dài nhất (nhiều cạnh nhất). Nếu có nhiều hành trình cùng độ dài, cô chọn hành trình có dãy nhãn nhỏ nhất theo thứ tự từ điển.

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $M$ .
$M$ dòng tiếp theo: Mỗi dòng gồm ba số nguyên $a_{i}$ , $b_{i}$ , $l_{i}$ — đường một chiều từ $a_{i}$ đến $b_{i}$ với nhãn $l_{i}$ ( $1 \leq l_{i} \leq 10^{9}$ ).

Dữ liệu ra

In ra $N$ dòng, dòng thứ $i$ gồm hai số nguyên: độ dài và giá trị của hành trình ưu tiên xuất phát từ thị trấn $i$ .

Ràng buộc

Không có hai đường cùng cặp thị trấn.
Các test $3$ - $4$ : $N, M \leq 5000$ và tất cả nhãn bằng nhau.
Các test $5$ - $8$ : $N, M \leq 5000$ và tất cả nhãn phân biệt.
Các test $9$ - $14$ : $N, M \leq 5000$ .
Các test $15$ - $20$ : Không có ràng buộc thêm.

Ví dụ

Input	Output	Giải thích
4 5 4 3 10 4 2 10 3 1 10 2 1 10 4 1 10	0 0 1 10 1 10 2 20	Thị trấn 1: không có đường ra, hành trình rỗng. Thị trấn 4: hai hành trình dài nhất 4→3→1 và 4→2→1 đều có độ dài 2 và cùng dãy nhãn [10, 10], nên giá trị = 20.

Bình luận

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