典型的 Floyd。

#include "bits/stdc++.h"using namespace std;int f[114][514];int a[114][514];int main() {int n;cin >> n;n += 2;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> a[i][j];f[i][j] = a[i][j];}}f[1][1] = 0;for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}}}cout << f[1][n];}