Description：

给一个无向图，边权均为 $a$ ，然后将原来图中满足最短路等于 $2a$ 所有的点对 $(x,y)$ 之间再加一条长度为 $b$ 的无向边，问操作之后点 $K$ 到所有点的最短路是多少

$1\le n \le 10^5,1\le a,b\le 1000$

Solution：

先分类讨论：

如果 $b\ge2a$ ，那么没用，最短路还是原来的最短路。

$a<b<2a$ ，把原来最短路每两个 $a$ 合并成一个 $b$ ，奇数个 $a$ 最后剩一个 $a$ 。

$b\le a$ ：这是最复杂的情况，因为有可能多走一步实现最后的合并，先考虑暴力，从当前点枚举每条出边，再枚举出边的出边，注意这些边对面的点不能与原来的点相邻，否则最短路不是 $2a$ ，用 $b$ 更新那些点，时间复杂度 $O(m^2)$ 是过不了的。

有一个小优化：如果从 $a$ 到了 $x$ ， $x$ 在第二轮枚举中又枚举到了 $y$ ，那么边 $(x,y)$ 及其反向边就都没用了，因为不可能循环更新，可以用双向边表来维护删除操作，看上去只能优化一些常数，但是实际上，每次删边之后 $x$ 只有另一边的点和 $a$ 距离也为一的点因为不是最短路而没有被删除，这些边最多有 $deg(a)^2$ 个，所以总复杂度是 $\begin{align}\sum_{v\in V}\min(deg[v]^2,m)\le\sum_{v\in V}\sqrt{deg(v)^2m}=\sum_{v\in V}deg(v)\sqrt m=O(m\sqrt m)\end{align}$

如果我们把 $a$ 到 $x$ 称为一次遍历， $x$ 到 $y$ 称为二次遍历，那么要对于这两次遍历建立两个边表，每次只在二次遍历的边表中删边，因为可能 $x$ 被加入队列，一次遍历可能需要 $x$ 到 $y$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,s,a,b;

#define MAXN 100010

struct edge_table

{

	struct edge

	{

		int to,nxt,pre;

	}e[MAXN << 1];

	int edgenum;

	int lin[MAXN];

	edge_table(){edgenum = 0;memset(lin,0,sizeof(lin));}

	void add(int a,int b)

	{

		++edgenum;e[edgenum].to = b;e[lin[a]].pre = edgenum;e[edgenum].nxt = lin[a];lin[a] = edgenum;

		++edgenum;e[edgenum].to = a;e[lin[b]].pre = edgenum;e[edgenum].nxt = lin[b];lin[b] = edgenum;

		return;

	}

	void del(int a,int i)

	{

		if(i == lin[a])lin[a] = e[i].nxt;

		e[e[i].pre].nxt = e[i].nxt;

		e[e[i].nxt].pre = e[i].pre;

		return;

	}

}g1,g2;

int d[MAXN],ans[MAXN];

bool vis[MAXN];

int main()

{

	scanf("%d%d%d%d%d",&n,&m,&s,&a,&b);

	int x,y;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&x,&y);

		g1.add(x,y);g2.add(x,y);

	}

	queue<int> q;q.push(s);

	memset(d,0x3f,sizeof(d));d[s] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = g1.lin[k];i != 0;i = g1.e[i].nxt)

		{

			if(d[g1.e[i].to] > d[k] + 1)

			{

				d[g1.e[i].to] = d[k] + 1;

				q.push(g1.e[i].to);

			}

		}

	}

	for(int i = 1;i <= n;++i)ans[i] = min(d[i] * a,d[i] / 2 * b + (d[i] % 2) * a);

	memset(d,0x3f,sizeof(d));

	q.push(s);d[s] = 0;

	memset(vis,false,sizeof(vis));

	while(!q.empty())

	{

		int k = q.front();q.pop();

		for(int i = g1.lin[k];i != 0;i = g1.e[i].nxt)

			vis[g1.e[i].to] = true;

		for(int i = g1.lin[k];i != 0;i = g1.e[i].nxt)

		{

			int v = g1.e[i].to;

			for(int j = g2.lin[v];j != 0;j = g2.e[j].nxt)

			{

				if(!vis[g2.e[j].to] && d[g2.e[j].to] > d[k] + 1)

				{

					d[g2.e[j].to] = d[k] + 1;

					q.push(g2.e[j].to);

					g2.del(v,j);

				}

			}

		}

		for(int i = g1.lin[k];i != 0;i = g1.e[i].nxt)

			vis[g1.e[i].to] = false;

	}

	for(int i = 1;i <= n;++i)ans[i] = min(ans[i],d[i] * b);

	for(int i = 1;i <= n;++i)printf("%d\n",ans[i]);

	return 0;

}