Chuyến Bay Giảm Giá

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ thành phố và $m$ chuyến bay một chiều. Bạn có một phiếu giảm giá dùng được đúng một lần, làm giảm giá chuyến bay đó xuống còn $⌊ c / 2 ⌋$ . 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 1: hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$ , $b$ , $c$ — chuyến bay từ $a$ đến $b$ với giá $c$ .

Dữ liệu ra

In chi phí nhỏ nhất để đến thành phố $n$ .

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$
$1 \leq c \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
3 4 1 2 3 2 3 1 1 3 7 2 1 5	2	Đường 1→2→3: dùng giảm giá cho chuyến 1→2: ⌊3/2⌋+1=2.

Bình luận

Không có bình luận tại thời điểm này.