Chặn Đường (Gold)

Đ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$ địa điểm được nối với nhau bởi $M$ con đường hai chiều. Mỗi con đường nối hai địa điểm $A$ và $B$ với độ dài $L$ . Một người đi từ địa điểm $1$ đến địa điểm $N$ theo đường đi ngắn nhất.

Một nhóm muốn cản trở việc di chuyển này bằng cách chặn một con đường — làm đôi độ dài của nó (nhân đôi). Nhóm sẽ chọn con đường để tối đa hóa mức tăng của đường đi ngắn nhất từ $1$ đến $N$ .

Hãy tính mức tăng lớn nhất có thể đạt được.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $M$ ( $1 \leq N \leq 250$ , $1 \leq M \leq 25000$ ).
$M$ dòng tiếp theo: Mỗi dòng gồm ba số nguyên $A$ , $B$ , $L$ — con đường nối địa điểm $A$ và $B$ có độ dài $L$ ( $1 \leq L \leq 10^{6}$ ).

Đồ thị liên thông, không có cạnh trùng lặp.

Dữ liệu ra

Một số nguyên duy nhất: mức tăng lớn nhất của đường đi ngắn nhất sau khi nhân đôi một con đường.

Ràng buộc

$1 \leq N \leq 250$
$1 \leq M \leq 25000$
$1 \leq L \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 đi ngắn nhất ban đầu là $1 \to 3 \to 4 \to 5$ với độ dài $6$ . Nếu nhân đôi cạnh $3$ - $4$ (từ $3$ thành $6$ ), đường ngắn nhất mới là $1 \to 3 \to 5$ với độ dài $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	Chặn cạnh duy nhất trên đường ngắn nhất làm tăng đáng kể khoảng cách.

Bình luận

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