python/TangDou/DiTui/ChengShiPath.cpp

#include <bits/stdc++.h>

using namespace std;

const int N=1000010;
int dp[N];
// 城市路径
// https://blog.csdn.net/weixin_43736974/article/details/108246801

int minPath = INT32_MAX, n;
vector<pair<int, int>> v1 = {{0, 0}}; //有一个元素，初值

//曼哈顿距离
int dis(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

//设f(i)为从城市1依次跳到城市i的距离之和
int f(int i) {
    if (i == 1) return 0;
    return dp(i - 1) + dis(v1[i - 1], v1[i]);
}

//设g(i)为从城市i依次跳到城市n的距离之和
int g(int i) {
    if (i == n) return 0;
    return g(i + 1) + dis(v1[i], v1[i + 1]);
}

int main() {
    //输入+输出重定向
    freopen("../DiTui/ChengShiPath.txt", "r", stdin);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        v1.push_back({x, y});
    }
    //输出
    for (int i = 1; i <= n; ++i) {
        cout << v1[i].first << " " << v1[i].second << endl;
    }

    for (int i = 2; i < n; i++) {
        minPath = min(minPath, dp(i - 1) + g(i + 1) + dis(v1[i - 1], v1[i + 1]));
    }
    cout << minPath << endl;
    //关闭文件
    fclose(stdin);
    return 0;
}