Phí Qua Trạm Thu Phí

Buổi 19 — Đường đi ngắn nhất
Points
28
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Mỗi đỉnh $i$ có một mức phí qua trạm là $A_i$, và mỗi cạnh $(u, v)$ có chi phí di chuyển $w$. Tổng chi phí của một đường đi là tổng chi phí các cạnh trên đường đi cộng với phí qua trạm của tất cả các đỉnh thuộc đường đi (bao gồm cả đỉnh xuất phát $1$ và đỉnh đích $N$). Hãy tìm tổng chi phí nhỏ nhất để đi từ $1$ đến $N$ (hoặc -1 nếu không đến được).

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $M$ ($1 \le N \le 10^5$, $0 \le M \le 2 \times 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 ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $0 \le w \le 10^9$).
Dữ liệu ra
  • In ra tổng chi phí nhỏ nhất từ $1$ đến $N$, hoặc -1 nếu không có đường đi.
Ví dụ
Input Output
4 4\n1 5 2 3\n1 2 2\n2 4 1\n1 3 4\n3 4 2 12
3 1\n5 5 5\n1 2 3 -1
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le M \le 2 \times 10^5$
  • $0 \le A_i, w \le 10^9$
Draft saved