#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; }

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

这题有点问题啊： 首先，输入数据； 然后初始化一个ans变量，将它初始化为r[1][n]的值（r[1][n]的含义是从码头1直接到码头n所需的租金数量）； 接着，枚举一下换乘点k，从2到n-1（注意，换乘点不为n，不然就是直接1~n了哈），我们的ans变量方程是这样的 ans=min(ans,r[1][k]+r[k][n]); 最后输出一下ans哈

完结撒花！