Editorial for Tuyến xe

Nhật xét 1: Cần xử lý với trường hợp đa đồ thị, chỉ lưu lại cạnh nhỏ nhất. Vì vậy có tối đa $n^2$ ~n^2~ cạnh.

Nhật xét 2: Đường đi ngắn nhất không thể chứa chu trình, vì vậy chỉ cần sử dụng tối đa $n-1$ ~n-1~ tuyến xe. Nếu $k \ge n$ ~k \ge n~ thì đáp án giống với trường hợp $k=n-1$ ~k=n-1~.

Gọi $dp[d][x][y]$ ~dp[d][x][y]~ là thời gian ngắn nhất di chuyển từ đỉnh $x$ ~x~ đến đỉnh $y$ ~y~ sử dụng tối đa $d$ ~d~ tuyến xe. Tiến hành duyệt qua các cạnh $[z,y]$ ~[z,y]~ với trọng số $w[z][y]$ ~w[z][y]~ để cập nhật:

$\displaystyle dp[d][x][y] = \min\{dp[d-1][x][z]+w[z][y]\}$

Độ phức tạp: $O(n^4)$ ~O(n^4)~.

Editorial for Tuyến xe

Tuyến xe

Comments