C/C++: Đường đi có tổng nhỏ nhất

SonLam89 · 27/10/16

Ai giải giúp mình bài tập này với.Cho 1 bảng số tự nhiên có kích thước M x N, và tọa độ dòng cột (X, Y) của 1 ô bất kỳ trong bảng. Tìm đường đi từ ô (X, Y) tới 1 cạnh biên bất kỳ của bảng sao cho tổng các số trên đường đi là nhỏ nhất. Biết răng từ 1 ô chỉ được di chuyển sang 1 ô chung cạnh (trên, dưới, trái, phải). M và N không quá 1000.

tengiday · 28/10/16

Mình nghĩ bài này dùng Dijkstra với heap là được. Mỗi một ô trên bảng là 1 vertex. Độ phức tạp của thuật toán là O(n^2 log n) ?.

SonLam89 · 30/10/16

tengiday:
Mình nghĩ bài này dùng Dijkstra với heap là được. Mỗi một ô trên bảng là 1 vertex. Độ phức tạp của thuật toán là O(n^2 log n) ?.

Ý tưởng của bạn đúng rồi. Mình đã làm được. Cám ơm bạn nhiều.

C/C++: Đường đi có tổng nhỏ nhất

tengiday

Happy life

SonLam89

Bài viết mới nhất

Thống kê

Bài viết được quan tâm nhiều