Chuyến bay giảm giá một chặng
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$
Community Discussion