Chuyến bay giảm giá một chặng

Buổi 73-74 — Virtual CF Graphs
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $n$ thành phố và $m$ chuyến bay một chiều. Chuyến bay thứ $i$ đi từ thành phố $a_i$ đến $b_i$ với giá vé $c_i$. Bạn có đúng một phiếu giảm giá giúp giảm một nửa giá vé của tối đa một chuyến bay bất kỳ (giá vé $c$ giảm xuống còn $\lfloor c / 2 \rfloor$). Hãy tìm chi phí nhỏ nhất để đi từ thành phố $1$ đến thành phố $n$.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $n, m$ ($2 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5$).
  • $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i, b_i, c_i$ ($1 \le a_i, b_i \le n, 1 \le c_i \le 10^9$). Đề bài đảm bảo có đường đi từ $1$ đến $n$.
Dữ liệu ra
  • Một số nguyên duy nhất là chi phí nhỏ nhất.
Ví dụ
Input Output
3 4
1 2 3
2 3 1
1 3 7
2 1 5
2
Giới hạn
  • $2 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5$
Draft saved