题目描述

长江游艇俱乐部在长江上设置了 nn 个游艇出租站 1,2,\cdots,n1,2,⋯,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 ii 到游艇出租站 jj 之间的租金为 r(i,j)r(i,j)（1\le i\lt j\le n1≤i<j≤n）。试设计一个算法，计算出从游艇出租站 11 到游艇出租站 nn 所需的最少租金。

输入格式

第一行中有一个正整数 nn，表示有 nn 个游艇出租站。接下来的 n-1n−1 行是一个半矩阵 r(i,j)r(i,j)（1\le i<j\le n1≤i<j≤n）。

输出格式

输出计算出的从游艇出租站 11 到游艇出租站 nn 所需的最少租金。

输入输出样例

输入

3
5 15
7
输出 
12

思路

一道平平无奇的floyd（x借助y到达z最短），题解似乎有用动规的（没看），唯一需要注意的点是这是有向图，一开始误解成无向图了。

floyd不了解的指路弗洛伊德算法，直接上代码。

#include <bits/stdc++.h>
using namespace std;
int a[201][201], n;
int main() {//有向图从1到n
	cin >> n;
	memset(a, 0x3f, sizeof(a));//∞
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			if (i == j) a[i][j] = 0;
			else {
				cin >> a[i][j];
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = i + 1; k <= n; k++) {
				if (a[j][i] + a[i][k] < a[j][k])
					a[j][k] = a[j][i] + a[i][k];
			}
		}
	}
	cout << a[1][n] << endl;
	return 0;
}