#include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; // 租金矩阵 vector<vector> r(n + 1, vector(n + 1, 0)); for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { cin >> r[i][j]; } } // dp[i]--从1到i的minn vector dp(n + 1, INT_MAX); dp[1] = 0; // 初始化 for (int i = 2; i <= n; i++) { // 1.直达 if (r[1][i] != 0) { dp[i] = min(dp[i], r[1][i]); } // 2.中转 for (int k = 2; k < i; k++) { // 检查是否存在 if (r[1][k] != 0 && r[k][i] != 0) { dp[i] = min(dp[i], r[1][k] + r[k][i]); } } } cout << dp[n]; return 0; }

由于仅能中转一次，所以分类讨论中转/直达两种方法，然后就直接模板收割