1. 每轮迭代只允许一只蚂蚁留下信息素。交替使用当前轮最优和历史最优。
2. 令蒸发量比较小以探索全图，并控制信息素在一个合理的区间。

令 $\beta=4$，$m=1.5n$。

对于 $n$ 较小的数据，令 $\alpha=1$ 或 $1.5$，$\rho=0.1$；对于 $n$ 较大的数据，令 $\alpha=2$，$\rho=0.05$。然后基本上就能一遍过大部分的点，并且能在大部分的点吊打 std。

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <random>
#include <string>

namespace {
using std::cin;
using std::clog;
using std::cout;
using std::endl;
using std::int64_t;
using std::size_t;

namespace base {
template <typename T, size_t... sizes>
struct NestedArray {};

template <typename T, size_t size, size_t... sizes>
struct NestedArray<T, size, sizes...> {
  using Type = std::array<typename NestedArray<T, sizes...>::Type, size>;
};

template <typename T>
struct NestedArray<T> {
  using Type = T;
};

template <typename T, size_t... sizes>
using Array = typename NestedArray<T, sizes...>::Type;

void OptimizeIO() {
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
}

void OptimizeIO(const std::string &input_file, const std::string &output_file) {
  static std::ifstream input_stream(input_file);
  static std::ofstream output_stream(output_file);
  cin.rdbuf(input_stream.rdbuf());
  cout.rdbuf(output_stream.rdbuf());
  cin.tie(nullptr), cout.tie(nullptr);
}
}  // namespace base

using base::Array;

const int kMaxN = 1005, kT = 200, kMinPheromone = 1, kMaxPheromone = 20;
const int64_t kInf = 1.0e18 + 5, kQ = 5.0e9;
const double kAlpha = 2, kBeta = 4, kRho = 0.9,
             kTau = std::pow(kMaxPheromone, kAlpha);
int n, m, type;
int64_t ans = kInf, res;
Array<int, kMaxN> path, it_best_path, his_best_path;
Array<bool, kMaxN> vis;
Array<int, kMaxN, kMaxN> g;
Array<double, kMaxN, kMaxN> eta, p, pheromone;
std::mt19937 rng(std::chrono::system_clock().now().time_since_epoch().count());

inline int RandInt(int l, int r) {
  return std::uniform_int_distribution<>(l, r)(rng);
}

inline double RandDouble(double l, double r) {
  return std::uniform_real_distribution<>(l, r)(rng);
}

void Go(int s) {
  path[1] = path[n + 1] = s;
  std::fill_n(vis.begin() + 1, n, false), vis[s] = true;

  for (int i = 2; i <= n; ++i) {
    int u = path[i - 1];
    double sum = 0;

    for (int j = 1; j <= n; ++j) {
      if (!vis[j]) sum += p[u][j];
    }

    double r = RandDouble(0, sum);

    for (int j = 1; j <= n; ++j) {
      if (vis[j]) continue;

      if (r <= p[u][j]) {
        path[i] = j, vis[j] = true;
        break;
      } else {
        r -= p[u][j];
      }
    }
  }

  int64_t len = 0;
  for (int i = 1; i <= n; ++i) len += g[path[i]][path[i + 1]];

  if (res > len) {
    res = len, std::copy_n(path.begin() + 1, n + 1, it_best_path.begin() + 1);
  }
}

void Update(const Array<int, kMaxN> &path, int64_t len) {
  double x = static_cast<double>(kQ) / len;
  for (int i = 1; i <= n; ++i) pheromone[path[i]][path[i + 1]] += x;
}

void Iterate() {
  res = kInf;
  for (int i = 1; i <= m; ++i) Go(RandInt(1, n));

  if (ans > res) {
    ans = res, clog << ans << endl;
    std::copy_n(it_best_path.begin() + 1, n + 1, his_best_path.begin() + 1);
  }

  type ^= 1;

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) pheromone[i][j] *= kRho;
  }

  type ? Update(his_best_path, ans) : Update(it_best_path, res);

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (pheromone[i][j] > kMaxPheromone) pheromone[i][j] = kMaxPheromone;
      if (pheromone[i][j] < kMinPheromone) pheromone[i][j] = kMinPheromone;
      p[i][j] = std::pow(pheromone[i][j], kAlpha) * eta[i][j];
    }
  }
}

int Main() {
  base::OptimizeIO();
  cin >> n, m = n * 1.5;

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> g[i][j];
      eta[i][j] = 1 / std::pow(g[i][j], kBeta), p[i][j] = kTau * eta[i][j];
    }

    std::fill_n(pheromone[i].begin() + 1, n, kMaxPheromone);
  }

  for (int i = 1; i <= kT; ++i) {
    Iterate();
    clog << "it #" << i << " done." << endl;
  }

  cout << ans << "\n";
  for (int i = 1; i <= n; ++i) cout << his_best_path[i] << "\n";
  return 0;
}
}  // namespace

int main() { return Main(); }