租用游艇

# 题意简述

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

# 题目分析

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

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

# 代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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