Điểm Số Cao Nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Có $n$ phòng và $m$ đường hầm một chiều. Bắt đầu từ phòng $1$ , mỗi đường hầm có điểm số (có thể âm). Tìm điểm số lớn nhất có thể đạt được khi đến phòng $n$ . Nếu có thể đạt điểm số tùy ý lớn, in $- 1$ .

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$ , $b$ , $x$ — đường hầm từ $a$ đến $b$ với điểm số $x$ .

Dữ liệu ra

In điểm số lớn nhất có thể đạt khi đến phòng $n$ , hoặc $- 1$ nếu điểm số không bị giới hạn.

Ràng buộc

$1 \leq n \leq 2500$
$1 \leq m \leq 5000$
$- 10^{9} \leq x \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 5 1 2 3 2 4 -1 1 3 -2 3 4 7 1 4 4	5	Đường 1→2→4: 3+(-1)=2; đường 1→3→4: -2+7=5.

Bình luận

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