Chặn Đường

Đ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

Cho đồ thị vô hướng $N$ đỉnh, $M$ cạnh có trọng số. Một người đi từ đỉnh $1$ đến đỉnh $N$ theo đường đi ngắn nhất.

Bạn được phép nhân đôi trọng số của đúng một cạnh. Hãy tìm cạnh tốt nhất để nhân đôi sao cho đường đi ngắn nhất mới tăng nhiều nhất so với ban đầu.

In ra độ tăng tối đa.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$
$M$ dòng tiếp theo: Ba số nguyên $A_{i}, B_{i}, L_{i}$ — cạnh nối $A_{i}$ với $B_{i}$ có trọng số $L_{i}$

Dữ liệu ra

In ra độ tăng tối đa của đường đi ngắn nhất.

Ràng buộc

$1 \leq N \leq 250$
$1 \leq M \leq 25 000$
$1 \leq L_{i} \leq 10^{6}$

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: 1→3→4→5 (dài 6). Nhân đôi cạnh 3-4 (3→6): đường mới 1→3→5 (dài 8). Tăng = 2

Bình luận

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