题解：P9377 [THUPC 2023 决赛] 百合

· · 题解

这题确实是好题。

我们记录状态 (u,i,j) 表示某个点的后 i 位修改了 j 位走到 u 的状态。我们不用管是那个点走过来的，因为只要能走过来的点可以更新这个点就没问题。

按照标准的 dijkstra 算法流程，我们从小根堆里面取出对顶，这时候堆顶的状态是 (u,0,0)。我们先按照原来图上的边转移，转移后再考虑更新能更新到且还没更新的 (v,i,j)。

因为我们从当前点到新点之间需要记录不同的 1 数量，且转移在这个新图上是相同的，因此我们可以走到以后按照是否让这一位不一样走向 未更新的 (v,i+1,j) 和 未更新的 (v\oplus 2^i,i+1,j+1) 两个状态，直到 i=k 的时候用 a_j 更新 dis_v 。我们考虑到新图上每条直接转移的边都用于 bfs，有权值的边会放到优先队列里面，而对于有权值的边，一部分是原来的，还有一部分是 (v,k,j) 连过来的，这部分由 v 和 j 决定，因此共有 m+k2^k 条，加上优先队列的 \log n 即 k，时间复杂度 O(mk+k^22^k)。

源代码：


#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
#define INF 1145141919810
using namespace std;

int n,m,k,s,dis[200005],a[20];
int vis[200005][18][18];
vector<pii> t[200005];
struct node{
    int u,dis;
    friend bool operator<(node a,node b){
        return a.dis>b.dis;
    }
};
struct node2{
    int u,i,j;
};
priority_queue<node> q;
queue<node2> qx;

void dijkstra(){
    q.push({s,0});
    while(!q.empty()){
        int u=q.top().u;q.pop();
        if(vis[u][0][0])continue;
        for(auto i:t[u]){
            if(vis[i.fi][0][0])continue;
            if(dis[i.fi]>dis[u]+i.se){
                dis[i.fi]=dis[u]+i.se;
                q.push({i.fi,dis[i.fi]});
            }
        }
        qx.push({u,0,0});
        while(!qx.empty()){
            int now=qx.fr.u,i=qx.fr.i,j=qx.fr.j;qx.pop();
            //cout<<now<<"\n";
            vis[now][i][j]=1;
            if(i==k){
                if(dis[now]>dis[u]+a[j])
                    dis[now]=dis[u]+a[j],q.push({now,dis[now]});
                continue;
            }
            if(!vis[now][i+1][j])qx.push({now,i+1,j});
            if(!vis[now^(1<<i)][i+1][j+1])qx.push({now^(1<<i),i+1,j+1});
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>k>>m>>s;n=(1<<k)-1;
    for(int i=1;i<=k;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        int u,v,c;cin>>u>>v>>c;
        t[u].push_back(mp(v,c));
        t[v].push_back(mp(u,c));
    }
    for(int i=0;i<=n;i++)dis[i]=INF;
    dis[s]=0;
    dijkstra();
    for(int i=0;i<=n;i++)cout<<dis[i]<<" ";
}