Chặn đường

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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$ nút và $M$ cạnh vô hướng có trọng số. Bạn cần đi từ nút $1$ đến nút $N$ theo đường đi ngắn nhất.

Một kẻ phá hoại có thể chọn đúng một cạnh và nhân đôi trọng số của cạnh đó, nhằm tối đa hóa độ dài đường đi ngắn nhất từ $1$ đến $N$ . Hãy tính mức tăng tối đa có thể xảy ra.

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$ , $L$ — cạnh nối nút $A$ và $B$ với trọng số $L$ .

Dữ liệu ra

Một số nguyên — mức tăng tối đa của đường đi ngắn nhất sau khi kẻ phá hoại chọn cạnh tối ưu.

Ràng buộc

$1 \leq N \leq 250$
$1 \leq M \leq 25000$
$1 \leq L \leq 10^{6}$
Đồ thị liên thông; không có nhiều cạnh giữa cùng một cặp nút.

Ví dụ

Input	Output	Giải thích
5 7 2 1 5 1 3 1 3 2 8 3 5 7 3 4 3 2 4 7 4 5 2	2	Đường ngắn nhất ban đầu: 1→3→4→5, độ dài 6. Nhân đôi cạnh 3-4 (3→6): đường ngắn nhất trở thành 1→3→5 = 8. Tăng 2.
10 9 4 10 12 8 4 24 4 6 10 4 2 11 3 6 18 5 10 11 5 7 24 1 7 5 1 9 17	24	Nhân đôi cạnh tối ưu làm tăng đường ngắn nhất thêm 24.

Bình luận

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