Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Người bán hàng rong (bitmask TSP)

    Cho nnn thành phố và ma trận khoảng cách dijd_{ij}dij​. Người bán hàng xuất phát từ thành phố 000, đi qua mỗi thành phố đúng một lần rồi quay về 000. Tìm tổng quãng đường nhỏ nhất (chu trình Hamilton ngắn nhất).

    • Định dạng đầu vào:

      Dòng đầu nnn. nnn dòng sau, mỗi dòng nnn số nguyên là ma trận khoảng cách (đối xứng, dii=0d_{ii}=0dii​=0).

    • Ràng buộc đầu vào:

      1≤n≤151 \le n \le 151≤n≤15, 0≤dij≤1060 \le d_{ij} \le 10^60≤dij​≤106.

    • Định dạng đầu ra:

      In một số nguyên: độ dài chu trình nhỏ nhất.

    Ví dụ:

    Đầu vào:

    4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

    Đầu ra:

    80

    Giải thích:

    Chu trình 0->1->3->2->0 = 10+25+30+15 = 80 là ngắn nhất.

    Đang tải editor...