[Luogu1359] 租用游艇 题解

正如很多$dalao$所说，$DP$确实是做这道题的一个好办法蛤

但是因为我今天正好在自学$Floyd$，所以这题我就用$Floyd$写了

反正这题$N$的范围很小，$O(N^3)$可以过

$Floyd$算法的主要思想就是：找到从$i$点通过一个或多个中转点（也可能没有）到达$j$点的最佳路线。

就是一道裸的$Floyd$

$code$

#define il inline
#define rg register
#define INF 0x3f3f3f3f //注意INF不能大于INT_MAX/2，不然就会爆int
#define maxN 200 + 1 
//以上是各种宏定义
#include <bits/stdc++.h>

int dis[maxN][maxN]; //dis[i][j]保存从i到j的最短租金

int main()
{
    rg int n; //定义n
    scanf("%d", &n);
    for(rg int i = 1; i < n; ++ i)
        for(rg int j = i + 1; j <= n; ++ j)
            scanf("%d", &dis[i][j]);
    for(rg int i = 1; i <= n; ++ i)
        for(rg int j = 1; j <= n; ++ j)
            if(!dis[i][j]) dis[i][j] = INF;
    //下面是Floyd算法的主要代码
    for(rg int k = 1; k <= n; ++ k) //枚举中转点k
        for(rg int i = 1; i <= n; ++ i)
            for(rg int j = 1; j <= n; ++ j)
                if(dis[i][j] > dis[i][k] + dis[k][j]) //如果有了更好的方案
                    dis[i][j] = dis[i][k] + dis[k][j]; //就更新dis[i][j]的值
    printf("%d", dis[1][n]); //输出从1到n的最低租金
    return 0;
}