[数据结构与算法]P1359 租用游艇

租用游艇 - 洛谷

dp

/*
 * @Description: To iterate is human, to recurse divine.
 * @Autor: Recursion
 * @Date: 2022-02-23 17:03:18
 * @LastEditTime: 2022-03-31 15:26:20
 */
#include<bits/stdc++.h>
#define Inf 0x3f3f3f
using namespace std;
const int N = 1e3;
int n;
int a[N][N];
int dp[N];

int main()
{
    while(cin>>n){
        for(int i = 1;i < n;i ++)//注意不能取等，dp为i到
            dp[i] = Inf;
        for(int i = 1;i <= n;i ++)
            for(int j = i + 1;j <= n;j ++)
                cin>>a[i][j];//i到j的费用
        for(int i = n - 1;i >= 1;i --)//从n-1开始到第1个
            for(int j = i + 1;j <= n;j ++)//从i + 1到n的最小花费
                dp[i] = min(dp[i],a[i][j] + dp[j]);
        cout << dp[1] << endl;
    }
}

floyd

/*
 * @Description: To iterate is human, to recurse divine.
 * @Autor: Recursion
 * @Date: 2022-03-31 16:46:13
 * @LastEditTime: 2022-03-31 17:06:02
 */
#include<bits/stdc++.h>
#define Inf 0x3f3f3f
using namespace std;
const int N = 1e4;
int a[N][N];
int n;
int main()
{
    while(cin >> n){
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                a[i][j] = Inf;
        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 k = 1;k <= n;k ++)
            for(int i = 1;i <= n;i ++)
                for(int j = 1;j <= n;j ++)
                    a[i][j] = min(a[i][j],a[i][k] + a[k][j]);
        cout << a[1][n] << endl;
    }
    
}

dijkstra:

/*
 * @Description: To iterate is human, to recurse divine.
 * @Autor: Recursion
 * @Date: 2022-03-31 17:16:03
 * @LastEditTime: 2022-03-31 17:31:22
 */
#include<bits/stdc++.h>
#define Inf 0x3f3f3f
using namespace std;
const int N = 1e4;
int a[N][N];
int n;
int main()
{
    while(cin >> n){
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                a[i][j] = Inf;
        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];
            }
        //dijstkra
        int dis[N],path[N];
        for(int i = 1;i <= n;i ++)
            dis[i] = a[1][i];
        memset(path,0,sizeof(path));
        dis[1] = 0;
        path[1] = 1;
        for(int i = 2;i <= n;i ++){
            int minn = Inf,u;
            for(int j = 1;j <= n;j ++){
                if(!path[j]&&dis[j] < minn){
                    minn = dis[j];
                    u = j;
                }
            }
            path[u] = i;
            for(int j = 1;j <= n;j ++){
                dis[j] = min(dis[j],dis[u] + a[u][j]);
            }
        }
        cout << dis[n];
    }
}