自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 22:57:55，当前版本为作者最后更新于2024-07-31 00:02:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题太难了。思考时间至少得有 1.5h，代码和 debug 难度也很高。放到正式比赛场上我不可能通过。

最初的观察

我们现在需要最小化棋子 $1$ 走到点 $T$ 的时间，假设棋子 $1$ 经过了 $c$ 个终止节点，那么 $2\sim K$ 号棋子分别需要走 $c$ 次。这时候我们容易发现剩下的棋子是独立的，我们只需要分别最小化他们的步数。

由于这是一张无向图，我们容易发现可以有一种很好的策略：先走到一个终止节点，从第二次开始每次走出一步再走回来，这样除了第一回合以外，每个回合对答案的贡献为固定的 $2$。

但是我们发现这样不一定是最优的：我们可能可以走到两个相邻的终止节点中的一个，并在两个终止节点之间反复横跳，这样除了第一回合以外每个回合只贡献 $1$ 的答案。那么很容易想到走到最近的终止节点 / 相邻的一组终止节点并反复横跳。很可惜，这样并非完全正确——走到相邻的终止节点的路径上可能有其他的终止节点。

巧妙的补丁

我们分析一下走到一组相邻终止节点的路径情况：假设路径上经过了 $c_1$ 个终止节点，路径长度为 $d$，而棋子 $1$ 总共经过了 $c$ 个终止节点，那么实际上贡献为 $d+c-c_1$。那么有个很简单的修补方式：将终止节点赋上 $-1$ 的权值，给边赋上 $1$ 的权值，这样跑 01 bfs。

你可能会好奇，这样为什么是对的？难道不会出现 $c_1>c$ 的路径被计算的情况吗？很容易分析出这种情况下，如果前 $c$ 个点中就已经有一对相邻点的，那么停在那个位置是更优的，否则如果不存在，每走一步，$d$ 增加至少 $2$，而 $c_1$ 只会增加 $1$，因此只会更劣。

问题的开端

现在 $2\sim K$ 每个棋子的代价可以被表示为 $\min(c+f_1,2c+f_2)$ 的形式。那么对于每个 $c$，剩下棋子的代价容易被计算出来（找出分段点，使用前缀和计算），是一个关于 $c$ 的函数 $F(c)$。

现在我们的问题清晰许多了：对于一条 $X_1\to T$ 的路径，如果长度为 $D$，经过了 $c$ 个终止节点，那么答案为 $\min(D+F(c))$。

在繁琐的分析之后我们之后得出了多项式时间复杂度的做法：记录当前的 $c$ 跑最短路，时间复杂度为 $\mathcal O(n^2)$。

最终的一击

考虑优化。我们发现当 $K$ 比较大的时候，我们肯定倾向于控制 $c$ 不要太大，因为 $c$ 一旦增加 $1$，代价至少会增加 $K-1$。我们容易分析得到，设 $X_1\to T$ 最少需要经过 $x$ 个终止节点，最优解经过了 $y$ 个终止节点，那么 $y-x$ 是 $\mathcal O(\frac{n}{K})$ 级别的。我们轻松把上面的做法优化到了 $\mathcal O(\frac{n^2}{K})$。

既然除以 $K$ 的字眼都出来了，再结合上部分分，最后一击只能是根号分治了。最后的最后，我们思考一下如何解决 $K$ 较小的情况。

容易发现 $F$ 这个函数是上凸的，且段数是 $\mathcal O(K)$ 级别的，因此我们可以取出这 $\mathcal O(K)$ 段线段并求解。如果我们将这条线段延申成直线，那么问题就好做了：把贡献拆到转移点上直接跑最短路。稍微分析一下就容易发现这样不可能把答案算小，且要算的答案肯定已经计算进去了。于是这部分是时间复杂度为 $\mathcal O(nK\log n)$。

平衡两边复杂度，取 $K=\mathcal O(\frac{\sqrt{n\log n}}{\log n})$，得到时间复杂度为 $\mathcal O(n\sqrt {n\log n})$。

代码细节相当繁琐。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=5e4+9,INF=1e12;
ll n,m,K,X[N],tod[2][N],tag[N],md[N],cst[N];
vector<ll>to[N];
char s[N];
void run1(){
    queue<ll>q;
    rep(i,0,n)tod[0][i]=-1;
    rep(i,1,n){
        if(s[i]=='1'){
            for(ll j:to[i])q.push(j),tod[0][j]=1;
        }
    }
    rep(i,1,n){
        if(~tod[0][i])q.push(i);
    }
    while(!q.empty()){
        ll u=q.front();q.pop();
        for(ll v:to[u]){
            if(!~tod[0][v]){
                tod[0][v]=tod[0][u]+1;
                q.push(v);
            }
        }
    }
}
void run2(){
    deque<ll>q;
    rep(i,0,n)tod[1][i]=-1;
    rep(i,1,n){
        if(tag[i]){
            for(ll j:to[i])tod[1][j]=1;
        }
    }
    rep(i,1,n){
        if(~tod[1][i])q.push_back(i);
    }
    while(!q.empty()){
        ll u=q.front();q.pop_front();
        for(ll v:to[u]){
            if(s[u]=='1'){
                if(!~tod[1][v]||tod[1][v]>tod[1][u])tod[1][v]=tod[1][u],q.push_front(v);
            }
            else {
                if(!~tod[1][v]||tod[1][v]>tod[1][u]+1)tod[1][v]=tod[1][u]+1,q.push_back(v);
            }
        }
    }
}
void run3(){
    rep(i,0,n)md[i]=INF;
    md[X[1]]=0;
    queue<ll>q;
    q.push(X[1]);
    while(!q.empty()){
        ll u=q.front();q.pop();
        if(u!=X[1]&&s[u]=='1')continue;
        for(ll v:to[u]){
            if(md[v]>md[u]+1){
                md[v]=md[u]+1;
                q.push(v);
            }
        }
    }
}
namespace S1{
    ll minc[N],f[N][505];
    void solve(){
        rep(i,1,n)minc[i]=INF;
        deque<ll>q;
        q.push_back(X[1]);
        minc[X[1]]=0;
        while(!q.empty()){
            ll u=q.front();q.pop_front();
            for(ll v:to[u]){
                ll w=(s[u]=='1'&&u!=X[1]);
                if(minc[v]>minc[u]+w){
                    minc[v]=minc[u]+w;
                    if(!w)q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
        rep(i,0,n){
            rep(j,0,min(500ll,n/K))f[i][j]=INF;
        }
        queue<pii>q1;
        f[X[1]][0]=0;
        q1.push({X[1],0});
        while(!q1.empty()){
            pii now=q1.front();q1.pop();
            ll u=now.first,i=now.second;
            for(ll v:to[u]){
                ll j=minc[u]+i-minc[v]+(u!=X[1]&&s[u]=='1');
                if(j<=min(500ll,n/K)){
                    if(f[v][j]>f[u][i]+1)f[v][j]=f[u][i]+1,q1.push({v,j});
                }
            }
        }
        rep(i,1,n){
            ll ans=md[i];
            rep(j,0,min(500ll,n/K))ans=min(ans,f[i][j]+cst[minc[i]+j]);
            write(ans),putchar('\n');
        }
    }
}
namespace S2{
    ll dis[N][2],ans[N];
    bool ok[N][2];
    struct Node{
        ll u,tp,d;
        bool operator<(const Node&a)const{return d>a.d;}
    };
    void dijk(ll k,ll sp){
        priority_queue<Node>q;
        rep(i,0,n+1){
            rep(j,0,1)dis[i][j]=INF,ok[i][j]=0;
        }
        dis[X[1]][0]=0;
        q.push({X[1],0,0});
        while(!q.empty()){
            Node now=q.top();q.pop();
            ll u=now.u,tp=now.tp;
            if(ok[u][tp])continue;
            ok[u][tp]=1;
            for(ll v:to[u]){
                ll w=1+k*(u!=X[1]&&s[u]=='1');
                ll ntp=tp||(u!=X[1]&&s[u]=='1');
                if(dis[v][ntp]>dis[u][tp]+w){
                    dis[v][ntp]=dis[u][tp]+w;
                    q.push({v,ntp,dis[v][ntp]});
                }
            }
        }
        rep(i,1,n)ans[i]=min(ans[i],sp+dis[i][1]);
    }
    void solve(){
        rep(i,1,n)ans[i]=md[i];
        rep(i,2,n){
            if(i==n||cst[i]*2!=cst[i-1]+cst[i+1])dijk(cst[i]-cst[i-1],cst[i]-(cst[i]-cst[i-1])*i);
        }
        rep(i,1,n)write(ans[i]),putchar('\n');
    }
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read(),m=read(),K=read();
    rep(i,1,m){
        ll x=read(),y=read();
        to[x].push_back(y);
        to[y].push_back(x);
    }
    scanf("%s",s+1);
    rep(i,1,K)X[i]=read();
    rep(i,1,n){
        if(s[i]=='1'){
            for(ll j:to[i]){
                if(s[j]=='1')tag[i]=1;
            }
        }
    }
    run1(),run2(),run3();
    if(!count(s+1,s+n+1,'1')){
        rep(i,1,n)write(md[i]),putchar('\n');
        return 0;
    }
    rep(i,2,K){
        cst[2]+=2;
        if(~tod[1][X[i]])cst[tod[1][X[i]]-tod[0][X[i]]+2]--;
    }
    rep(i,2,n)cst[i]+=cst[i-1];
    rep(i,2,K)cst[1]+=tod[0][X[i]];
    rep(i,2,n)cst[i]+=cst[i-1];
    if(K>=100)S1::solve();
    else S2::solve();
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}