专栏文章

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

MMoanran
P13534题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min4o5vb
此快照首次捕获于
2025/12/01 20:31
3 个月前
此快照最后确认于
2025/12/01 20:31
3 个月前
查看原文

题目 The way home / 回家的路

题目链接 CF1801D / 洛谷 P13534
P13534 The way home / 回家的路

题意简述

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

说明/提示

评分说明

本题测试数据分为 66 组。只有通过某一组的全部测试点，且通过部分之前组的全部测试点后，才能获得该组分数。有些分组不要求通过样例测试点。离线评测表示该组的测试结果会在比赛结束后公布。
组别分值nnmmsis_iwiw_i必须通过的组备注
00----------样例测试点
114------wi=1w_i=1--
213--m=n−1m = n - 1------ai=ia_i = i，bi=i+1b_i = i + 1
317n≤10n \le 10------0
419n≤100n \le 100--si≤100s_i \le 100--0
521n≤100n \le 100------0, 3, 4
616--------0--5离线评测

部分分1

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

部分分2

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

部分分3

我们思考一下，如果这道题只是简单的最短路，那 n,mn,m 的范围未免太小了，甚至都可以我们跑全源最短路了。对于组别 44 值域非常小，从这里切入。
我们再想我们来到一个城市的时候，我们其实只需要关注两件事，第一个是前面表演了几次，另一个是到这里剩下的钱。
我们设 dp 状态 fi,jf_{i,j} 表示到达 ii 号城市，已经表演了 jj 次，剩下的最大钱数。由于值域并不大，我们可以直接转移每一个演出次数，我们记 maxsmaxs 为 max⁡i=1nsi\max_{i=1}^{n}s_i，那总的表演次数不超过 maxs×nmaxs \times n，总的状态数会有 n2×maxsn^2 \times maxs 个，又因为我们要遍历每次出边，以及维护一个优先队列，总时间复杂度为 O(maxs×n2×m×log⁡n)O(maxs \times n^2 \times m \times \log n)。
此时期望得分来到了 4646 分。
想一想瓶颈再哪里，是在枚举方案到值域的过程，考虑优化。

部分分4

纵使完成题目的过程中可能会不完美，但谁都期望自己能够完美的做出这题，在部分分 33 的基础上，我们继续往前推出完美解法。
发现我们结合部分分 22 的想法上，贪心地保留经过的路径中，wiw_i 最大的顶点。
设状态 fi,jf_{i,j} 表示，当前走到了顶点 ii，最优演出的顶点为 jj，转移过程中存储表演次数和剩余钱数，不难结合部分分 33 的转移过程发现，我们应该让表演次数更小的同时，让剩余钱数最大。
首先 ii 和 jj 的可能情况最多有 n2n^2 种，我们会在这个过程中遍历所有出边，应该会有 n2+n×mn^2 + n \times m 次遍历，我们使用优先队列维护一个类似与最短路求法的转移方程，会带一个 log⁡n\log n 的复杂度。
总时间复杂度为 O(n2×m×log⁡n)O(n^2 \times m \times \log n)。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...