题解：P13534 [OOI 2023] The way home / 回家的路

· · 题解

题目 The way home / 回家的路

题目链接 CF1801D / 洛谷 P13534

P13534 The way home / 回家的路

题意简述

我们给定 1 到 n 之间存在 m 条带权有向边，找到存在一条路径到达节点 n 的时候，借助点权 w_i 的次数，增加当前剩余钱数的最小值。

说明/提示

评分说明

本题测试数据分为 6 组。只有通过某一组的全部测试点，且通过部分之前组的全部测试点后，才能获得该组分数。有些分组不要求通过样例测试点。离线评测表示该组的测试结果会在比赛结束后公布。

组别 分值 n m s_i w_i 必须通过的组 备注
0 0 -- -- -- -- -- 样例测试点
1 14 -- -- -- w_i=1 --
2 13 -- m = n - 1 -- -- -- a_i = i，b_i = i + 1
3 17 n \le 10 -- -- -- 0
4 19 n \le 100 -- s_i \le 100 -- 0
5 21 n \le 100 -- -- -- 0, 3, 4
6 16 -- -- -- -- 0--5 离线评测

部分分1

首先对于组别 1 来说，所有的 w_i 是等价的，并且每一场演出的贡献都是 1，那么我们直接找到 1 到 n 的最短路长度减去当前剩余钱数 p 即可。
写完之后存在一个小坑点，如果最短路比 p 还小，直接输出 0，所以答案要和 0 取最大值。

期望得分 14 分。

部分分2

组别 2 是一条链的特殊情况，我们想到如果要走到 n，我们必然会经过每个点，为了让我们的表演次数尽可能的少，我们想到尽可能在 w_i 更大的位置表演，于是我们直接维护一个前缀最大值，如果无法经过一条边，直接在前缀最大值的位置表演是一定更优的。

经过特判后期望得分 27 分。

部分分3

我们思考一下，如果这道题只是简单的最短路，那 n,m 的范围未免太小了，甚至都可以我们跑全源最短路了。对于组别 4 值域非常小，从这里切入。

我们再想我们来到一个城市的时候，我们其实只需要关注两件事，第一个是前面表演了几次，另一个是到这里剩下的钱。

我们设 dp 状态 f_{i,j} 表示到达 i 号城市，已经表演了 j 次，剩下的最大钱数。由于值域并不大，我们可以直接转移每一个演出次数，我们记 maxs 为 \max_{i=1}^{n}s_i，那总的表演次数不超过 maxs \times n，总的状态数会有 n^2 \times maxs 个，又因为我们要遍历每次出边，以及维护一个优先队列，总时间复杂度为 O(maxs \times n^2 \times m \times \log n)。

此时期望得分来到了 46 分。
想一想瓶颈再哪里，是在枚举方案到值域的过程，考虑优化。

部分分4

纵使完成题目的过程中可能会不完美，但谁都期望自己能够完美的做出这题，在部分分 3 的基础上，我们继续往前推出完美解法。

发现我们结合部分分 2 的想法上，贪心地保留经过的路径中，w_i 最大的顶点。

设状态 f_{i,j} 表示，当前走到了顶点 i，最优演出的顶点为 j，转移过程中存储表演次数和剩余钱数，不难结合部分分 3 的转移过程发现，我们应该让表演次数更小的同时，让剩余钱数最大。

首先 i 和 j 的可能情况最多有 n^2 种，我们会在这个过程中遍历所有出边，应该会有 n^2 + n \times m 次遍历，我们使用优先队列维护一个类似与最短路求法的转移方程，会带一个 \log n 的复杂度。

总时间复杂度为 O(n^2 \times m \times \log n)。

#include<iostream>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
struct Qi
{
    int to;
    int next;
    ll w;
} edge[3005];
int head[805], edge_cnt;
ll w[805];  // 每个节点的表演收益
// f[pos][best]={最小表演次数, 剩余金钱}，best表示当前最优表演城市
struct X
{
    ll num;  // 表演次数
    ll money;    
}f[805][805];
struct L
{
    int pos;      // 当前节点
    int best;     // 当前最优表演城市
    ll num;  // 表演次数
    ll money;
    friend bool operator < (L a, L b)
    {
        if (a.num!=b.num)
        {
            return a.num>b.num;
        }
        return a.money<b.money;
    }
};
priority_queue<L> Q;
void add(int u,int v,ll s)
{
    edge_cnt++;
    edge[edge_cnt].to=v;
    edge[edge_cnt].next=head[u];
    edge[edge_cnt].w=s;
    head[u]=edge_cnt;
}
int main()
{
    int n,m,p,g;
    cin>>n>>m>>p>>g;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j].num=1e18;
            f[i][j].money=0;
        }
    }
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=m;i++)
    {
        int u,v,s;
        cin>>u>>v>>s;
        add(u,v,s);
    }
    f[1][1].num=0;
    f[1][1].money=p;
    Q.push({1,1,0,p});
    while(!Q.empty())
    {
        L curr=Q.top();
        Q.pop();
        int u=curr.pos;
        int best=curr.best;
        ll curr_show=curr.num;
        ll curr_money=curr.money;
        // 若当前状态不是最优，跳过
        if(curr_show>f[u][best].num) continue;
        if(curr_show==f[u][best].num&&curr_money<f[u][best].money) continue;
        for (int i=head[u]; i; i=edge[i].next)
        {
            int v=edge[i].to;
            ll s=edge[i].w;
            ll now_show=curr_show;
            ll now_money=curr_money;
            int now_best=best;
            // 若当前金钱不足支付路径费用，需在最优城市表演补足
            if(now_money<s)
            {
                ll need=s-now_money;
                ll add_show=(need+w[now_best]-1)/w[now_best];
                now_show+=add_show;
                now_money+=add_show*w[now_best];
            }
            now_money-=s;
            if(w[v]>w[now_best]) now_best=v;
            // 若新状态更优，更新并加入队列
            if(now_show<f[v][now_best].num)
            {
                f[v][now_best].num=now_show;
                f[v][now_best].money=now_money;
                Q.push({v,now_best,now_show,now_money});
            }
            else if(now_show==f[v][now_best].num&&now_money>f[v][now_best].money)
            {
                f[v][now_best].money=now_money;
                Q.push({v,now_best,now_show,now_money});
            }
        }
    }
    ll ans=1e18;
    for(int best=1;best<=n;best++)
    {
        if(f[n][best].num<ans)
        {
            ans=f[n][best].num;
        }
    }
    cout<<(ans==1e18 ? -1:ans)<<endl;
    return 0;
}