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

· · 题解

Sol

不难想到，对于一条路径，表演操作必然形如，在路径上 w 各个前缀最大值处进行若干次使得恰好可以到达下一个前缀最大值处。这么贪心显然是不劣的。

然后就不知道怎么做了。观察数据范围，发现 n\le 800，于是考虑暴力。直接拆点，把每个位置的每种可能的前缀 w 最大值状态都拆出来，形成 O(n^2) 个点，然后跑最短路即可。

还有一个问题，就是我们貌似要同时在意当前的表演次数与剩余钱数，然而事实上只需要在保证表演次数最小的前提下最大化剩余钱数即可。由于我们的贪心策略是只在前缀最大值上操作恰需要的次数，因此操作更多的方案，既然操作过了，其剩余钱数必然不超过上一步的前缀最大值，故而操作更少的方案在当前前缀最大值处额外操作一次就能得到不少于那种方案的剩余钱数。

Code

const int N=805,NN=800*800+5;

int n,m,testid,v,nn;
ll p,xv[N];
vec<pil> g[N];
int id[N][N],w[N],to[NN],lv[NN];
pll dis[NN];

inline void Main(){
    cin>>n>>m>>p;
    nn=0;rep(i,1,n)g[i].clear();
    rep(i,1,n)cin>>w[i],xv[i]=w[i];
    sort(xv+1,xv+1+n),v=unique(xv+1,xv+1+n)-xv-1;
    rep(i,1,n)w[i]=lower_bound(xv+1,xv+1+v,w[i])-xv;
    rep(i,1,n)rep(j,1,v)id[i][j]=++nn,to[nn]=i,lv[nn]=j;
    rep(i,1,m){
        int a,b,c;cin>>a>>b>>c;
        g[a].pub({b,c});
    }
    rep(i,1,nn)dis[i]={INF,INF};
    dis[id[1][w[1]]]={0,-p};
    lrheap<pair<pll,int>> pq;
    pq.push({dis[id[1][w[1]]],id[1][w[1]]});
    while(pq.size()){
        auto tp=pq.top();pq.pop();
        if(tp.fir!=dis[tp.sec])continue;
        int x=tp.sec;
        for(auto e:g[to[x]]){
            int yd=e.fir;ll nd=e.sec;
            int y=id[yd][max(lv[x],w[yd])];
            ll tm=(-dis[x].sec>=nd?0:(nd+dis[x].sec+xv[lv[x]]-1)/xv[lv[x]]);
            if(dis[y]>(pll){dis[x].fir+tm,-(-dis[x].sec-nd+tm*xv[lv[x]])}){
                dis[y]=(pll){dis[x].fir+tm,-(-dis[x].sec-nd+tm*xv[lv[x]])};
                pq.push({dis[y],y});
            }
        }
    }
    ll ans=INF;
    rep(j,1,v)chmin(ans,dis[id[n][j]].fir);
    put(ans==INF?-1:ans);
}