可将旅行商的路线看作是从n - 1号点出发, 跳着到0号点, 再折返走完之前跳过的点. 想到这个, 暴力就可以得50分.

正解是DP.

f[i][j](i > j)表示, 从i开始跳, 并返回至j所需要的最小花费(从定义上i, j可互换)

因而得到递推式:

f[i + 1][i] = min(f[i + 1][i], f[i][j] + w[j][i + 1])

f[i + 1][j] = min(f[i + 1][j], f[i][j] + w[i][i + 1])

#include<iostream>

#include<string.h>

#include<algorithm>

using namespace std;

const int maxN = 1500;

int w[maxN][maxN];

int f[maxN][maxN];

int main()

{

    freopen("putnik.in", "r", stdin);

    freopen("putnik.out", "w", stdout);

    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    for(int i = 0; i < n; i ++)

        for(int j = 0; j < n; j ++)

            cin >> w[i][j];

    memset(f, 127, sizeof(f));

    f[0][0] = 0;

    for(int i = 0; i < n; i ++)

        for(int j = 0; j <= i; j ++)

            if(f[i][j] < (int)2e9)

                f[i + 1][i] = min(f[i + 1][i], f[i][j] + w[j][i + 1]),

                f[i + 1][j] = min(f[i + 1][j], f[i][j] + w[i][i + 1]);

    int ans = (int)2e9;

    for(int i = 0; i < n; i ++)

        ans = min(ans, f[n - 1][i]);

    cout << ans;

}