kết quả từ 1 tới 3 trên 3

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

  1. #1
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 347270
    Bài gửi
    4

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

    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.
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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) ?.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 347270
    Bài gửi
    4

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

    Trích Nguyên văn bởi tengiday Xem bài viết
    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.

  5. Đã cảm ơn SonLam89: