題目敘述

給一個 $n$ 個點的無向加權完全圖，點的編號為 $1, 2, \ldots, n$。編號 $i$ 和 $j$ 的點之間的邊權重為 $(i+j)\bmod (n+1)$。 求這個圖的最小權重 Hamiltonian Path。

題解

不難發現其中一種最佳路徑是 $1, n, 2, n-1, \ldots, \lceil n/2\rceil$。

參考程式碼

// by tmt514
#include <cstdio>

int main(void) {
  int n;
  scanf("%d", &n);
  printf("%d\n", (n-1)/2);
  return 0;
}