租用游艇

租用游艇【dp/最短路】

题目描述

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

输入格式

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

输出格式

输出计算出的从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金。

样例输入

3
5 15
7

样例输出

12

提示

$n\le 200$，保证计算过程中任何时刻数值都不超过 $10^6$。

思路

模板题，没啥好讲的…

注意到是从1到n，因此可以当成是单源最短路（Dijkstra）。$O((n+m)logn)$

又因为$n\le 200$，因此，可以用Floyd算法。$O(n^3)$

对于dp，设 dp[i] 是 从 1 到 i 的最小消费。$O(n^2)$

CODE

Dijkstra

struct GRA
{
    int n;
    vector<bool> vis;
    vector<int> dist, p;
    vector<vector<pair<int, int>>> adj;
    GRA(int n_) {init(n_);}
    void init(int n_)
    {
        n = n_;
        adj.resize(n + 1);
        p.resize(n + 1, -1);
        dist.resize(n + 1, inf);
        vis.resize(n + 1, false);
    }
    vector<int> find_path(int x)
    {
        vector<int> path;
        while (p[x] != -1)
        {
            path.push_back(x);
            x = p[x];
        }
        return vector<int>(rall(path));
    }
    struct cmp {bool operator()(const pair<int, int> x, pair<int, int> y) const {return x.second > y.second;}};
    void dijkstra(int u)
    {
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
        dist[u] = 0;
        q.push({u, dist[u]});
        while (!q.empty())
        {
            auto [pre, dis] = q.top();  q.pop();
            if (vis[pre])   continue;
            vis[pre] = true;
            for (auto [to, val] : adj[pre])
            {
                if (!vis[to] && dis + val < dist[to])
                {
                    dist[to] = dist[pre] + val;
                    p[to] = pre;
                    q.push({to, dist[to]});
                }
            }
        }
    }
};

void solve()
{
    int n, x;  cin >> n;
    GRA g(n);
    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            cin >> x;
            g.adj[i].push_back({j, x});
        }
    }

    g.dijkstra(1);
    cout << g.dist[n];
}

Floyd

void solve()
{
    int n;  cin >> n;
    vector<vector<int>> dis(n + 1, vector<int>(n + 1, inf));
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            cin >> dis[i][j];
    for (int i=1;i<=n;i++)
        dis[i][i] = 0;

    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (dis[i][k] != inf && dis[k][j] != inf && dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
    cout << dis[1][n];
}

dp

void solve()
{
    int n;  cin >> n;
    vector<vector<int>> v(n + 1, vector<int>(n + 1, inf));
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            cin >> v[i][j];

    vector<int> dp(n + 1, inf);
    dp[1] = 0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<i;j++)
            dp[i] = min(dp[i], dp[j] + v[j][i]);
    cout << dp[n];
}