Luogu

分析

显然最短路只有三种可能：

• 全走 $a$ 边。
• 把两条 $a$ 边看成一条 $b$ 边，如果还剩一条 $a$ 边就走 $a$ 边。
• 全走 $b$ 边。

前两种只需要简单 0/1 BFS 一遍即可，关键在于第三种如何处理。

有一个显然的 $\mathcal{O}(m^2)$ 思路是，枚举 $u$ 的出边 $v$ 和 $v$ 的出边 $w$，如果 $u,w$ 间没有连边就用 $u$ 更新 $w$。

这个东西感觉和三元环计数有一点点像，因此我们考虑怎么优化。我们维护两个边集，一个就是原图，另一个一开始是原图但要支持删边。我们枚举 $u$，然后枚举第一个边集中它的出边 $v$ 并标记，然后枚举第二个边集中 $v$ 的出边 $w$，如果 $w$ 没有被标记就更新 $w$ 然后把 $(v,w)$ 从第二个边集中删掉。

这样子复杂度是 $\mathcal{O}(m\sqrt{m})$ 的，因为三元环数量是 $\mathcal{O}(m\sqrt{m})$ 的，而不在三元环中的边都只会被删一次。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,s,a,b,ans[N],dis[N],vis[N];
vector<int> E[N];
unordered_set<int> S[N];
queue<int> Q;

int main() {
    n=read(),m=read(),s=read(),a=read(),b=read();
    for (int i=1;i<=m;++i) {
        int u=read(),v=read();
        E[u].emplace_back(v),E[v].emplace_back(u);
        S[u].insert(v),S[v].insert(u);
    }
    memset(dis,-1,sizeof(dis)); dis[s]=0,Q.push(s);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (int v:E[u])
            if (!~dis[v]) dis[v]=dis[u]+1,Q.push(v);
    }
    for (int i=1;i<=n;++i)
        ans[i]=min(dis[i]*a,(dis[i]>>1)*b+(dis[i]&1)*a);
    memset(dis,-1,sizeof(dis)); dis[s]=0,Q.push(s);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (int v:E[u]) vis[v]=1;
        for (int v:E[u]) {
            vector<int> del;
            for (int w:S[v]) {
                if (vis[w]) continue;
                if (!~dis[w]) dis[w]=dis[u]+1,Q.push(w);
                del.emplace_back(w);
            }
            for (int w:del) S[v].erase(w);
        }
        for (int v:E[u]) vis[v]=0;
    }
    for (int i=1;i<=n;++i) if (~dis[i]) ans[i]=min(ans[i],dis[i]*b);
    for (int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}