题解：P11327 [NOISG 2022 Finals] Voting Cities

· · 题解

P11327 [NOISG 2022 Finals] Voting Cities

Algorithm:

分层图最短路。

Solution:

看到 5 张优惠券就笑了，分层最短路的感觉又回来了。

按照使用了多少张优惠券进行分层，记状态 o 的第 i 位二进制位为第 i 张优惠券的使用情况，跑一边分层图最短路求最小值即可。

分层图最短路是指题目中有 k 种操作可以使通过一条路径的代价减少，但是会带来一定的代价，求最后的最短路。对于此，考虑类似 DP 的思想，记 dis_{i,j} 为从起点到第 i 个节点，花费的操作状态为 j（有些题目可以不用记录状态，记录使用了几次操作）。转移可以写作：

dis_{v,\operatorname{op}(j)}=\min(\min_{u \to v}dis_{u,j}+w,dis_{u,\operatorname{op}(j)}+\operatorname{op}(w))

其中代表此次操作对状态与边权的改变，w 为这条边的边权。跑一边最短路计算即可。

Code:

namespace Mr_Az{
    const int M=5008,N=M*35;
    int T=1;
    int n,m,q,k;
    int a[N],p[10],dis[N];
    bool vis[N];
    vector<pii> e[N];
    inline int id(int x,int y){return x*n+y;}
    inline void dij(){
        mem(dis,inf);mem(vis,0);
        priority_queue<pii> q;
        while(q.size()) q.pop();
        for(rint i=1;i<=k;i++) q.push({0,id(0,a[i])}),dis[id(0,a[i])]=0;
        while(q.size()){
            auto [azzzz,u]=q.top();q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(auto [v,w]:e[u]){
                if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                    q.push({-dis[v],v});
                }
            }
        }
        return ;
    }
    inline void solve(){
        read(n,m,k);
        for(rint i=1;i<=k;i++) read(a[i]),a[i]++;
        for(rint i=1,u,v,w;i<=m;i++){
            read(u,v,w);u++;v++;swap(u,v);
            for(rint s=0;s<(1<<5);s++){
                e[id(s,u)].eb(id(s,v),w);
                for(rint j=0;j<5;j++){
                    if(((s>>j)&1)==0){
                        e[id(s,u)].eb(id(s+(1<<j),v),w/10*(9-j));
                    }
                }
            }
        }
        dij();
        read(q);
        while(q--){
            int st,ans=-1,res=0;
            read(st);for(rint i=0;i<5;i++) read(p[i]);
            st++;
            for(rint s=0;s<(1<<5);s++){
                res=dis[id(s,st)];
                if(res==dis[0]) goto nxt;
                for(rint i=0;i<5;i++){
                    if((s>>i)&1){
                        if(p[i]==-1) goto nxt;
                        res+=p[i];
                    }
                }
                if(ans==-1) ans=res;
                else ans=min(ans,res);
                nxt:;
            }
            printf("%lld\n",ans);
        }
    }
    inline void mian(){if(!T) read(T);while(T--) solve();}
}