# 题意简述

长江上有n个游艇出租站,有一个游客想从上游1乘坐游艇到达n。每个站点到达另一个站点所需要的花费是不一样的,游客就想有没有一个好的方案,使所需要的花费最少。

# 题目分析

这道题其实就是一个单源最短路径,即Dijkstra算法,是一道非常经典的算法题。难就难在如何存储数据信息,因为输入的是一个半矩阵,开始我还看不懂这个半矩阵代表什么意思,后来明白了,半矩阵的第一行就代表从第一个点到下游各个点所需要花费的钱,第二行就可以以此类推了。存储也让我受了一些挫折,找不到一个好的存储方式,最后我是以它们实际存在的意义,所建立一个二维方程组,假如第一行存储的是第一个点到其余个点之间的距离,那么我就用f[i][j]代表站点i到站点j之间的所需要花费的钱数(权重),例如f[1][3]代表站点1到站点3之间所要花费的钱数,以此类推。

接下来就是运用迪杰斯特拉算法的思想了,由局部最优推广到全局最优,列举f[1][x]1x之间的每一个可能的分割点y,取最优值,状态转移方程如下f[1][x]=min(f[1][x],f[1][y]+f[y][x]),直到x=n,就可以取到最优值了。

# 代码如下

#include <iostream>
#include <algorithm>
using namespace std;
int f[205][205];//i代表起始点,j代表终点
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        fill(f[i], f[i] + n, 0);
    }
    for (int i = 1; i < n; i++)//下标都从1开始
    {
        for (int j = i + 1; j <= n; j++)
        {
            cin >> f[i][j];
        }
    }
    for (int i = 3; i <= n; i++)
    {
        for (int j = 2; j < i; j++)
        {
            f[1][i] = min(f[1][i], f[1][j] + f[j][i]);
        }
    }
    cout << f[1][n];//最终结果
  //  system("pause");
    return 0;
}