Đường đi ngắn nhất với vé giảm nửa

Buổi 19 — Đường đi ngắn nhất Buổi 69-70 — Mock Tổng hợp Graphs
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho đồ thị có hướng gồm $N$ đỉnh và $M$ cạnh có trọng số không âm. Cạnh thứ $i$ đi từ $u_i$ đến $v_i$ với chi phí $w_i$. Bạn có 1 vé giảm giá cho phép giảm một nửa chi phí của tối đa một cạnh trên đường đi (tức $w_i$ trở thành $\lfloor w_i / 2 \rfloor$). Hãy tìm chi phí nhỏ nhất để đi từ đỉnh $1$ đến đỉnh $N$, hoặc in ra -1 nếu không thể đi đến $N$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, M$.
  • $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i, v_i, w_i$.
Dữ liệu ra

In ra một số nguyên duy nhất là chi phí nhỏ nhất, hoặc -1.

Ví dụ
Input Output
3 4
1 2 3
2 3 1
1 3 7
2 1 5
2
Giới hạn

$1 \le N \le 10^5$, $0 \le M \le 2 \cdot 10^5$, $0 \le w_i \le 10^9$.

Draft saved