Hành trình săn thưởng từ 1 đến N
Points
80
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một bản đồ gồm $N$ khu vực và $M$ con đường một chiều (có thể tạo thành chu trình). Tại khu vực $i$ có phần thưởng trị giá $a_i$ điểm. Người chơi bắt đầu tại khu vực $1$ và cần đi tới khu vực $N$. Người chơi có thể đi qua một khu vực nhiều lần nhưng phần thưởng tại mỗi khu vực chỉ được nhận tối đa một lần.
Hãy tìm tổng điểm lớn nhất có thể đạt được trên một hành trình từ $1$ đến $N$, hoặc in ra -1 nếu không thể đi từ $1$ đến $N$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($0 \le a_i \le 10^9$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
In ra tổng điểm lớn nhất trên hành trình từ $1$ đến $N$, hoặc -1 nếu không có đường đi.
Ví dụ
| Input | Output |
|---|---|
| 5 6 10 20 30 40 50 1 2 2 3 3 1 2 4 4 5 1 5 |
150 |
| 4 2 5 10 15 20 1 2 3 4 |
-1 |
Giới hạn
$1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$, $0 \le a_i \le 10^9$.
Community Discussion