题目链接：[POI2013] CEN-Price List

考虑答案的可能情况：

1. 边权均为 $a$。
2. 边权均为 $b$。
3. 最后一条边边权为 $a$，其余边权为 $b$。

前面两种情况很好求。

令原图中路径长度为 $1$。

则答案分别为 $len\times a$ 和 $\frac{len}{2}\times b$。

但如果 $len$ 为奇数，此时如果均改为 $b$ 最后会剩下一条边，这时就是第三种情况。

正常的 BFS 是每次向外拓展一条边，但这里要求偶数条边，因此我们可以每次向外拓展两条边。

每次选中一个点 $u$，枚举和它连接的 $v$，再连接和它连接的 $w$。

如果 $u,w$ 间没有边相连，则可以直接遍历到 $w$。

因为这是 BFS，所以第一次遍历到一个点时一定是最短路。那么当一条边被当作第二条边遍历了，那么以后就不用考虑它了，直接删除即可。这样每次遍历到就删掉了，每条边只会当一次第二条边。删除可以用 STL list 维护。只有三元环中的两条边不会被删，有 $O\left(m\sqrt m\right)$ 条三元环，因此时间复杂度为 $O\left(m\sqrt m\right)$。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, m, S, A, B, vis[100005], dis[100005], ans[100005], isedge[100005];

struct node
{
	int u, v, w;
} edge[100005];

vector < int > G1[100005];

list < int > G2[100005];

queue < int > q;

int main()
{
	cin >> n >> m >> S >> A >> B;
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		G1[u].push_back(v);
		G2[u].push_back(v);
		G1[v].push_back(u);
		G2[v].push_back(u);
	}
	q.push(S);
	vis[S] = 1;
	dis[S] = 0;
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		for (int i = 0; i < G1[t].size(); i++)
		{
			int v = G1[t][i];
			if (!vis[v])
			{
				dis[v] = dis[t] + 1;
				vis[v] = 1;
				q.push(v);
			}
		}
	}
	for (int i = 1; i <= n; i++)
		ans[i] = min(dis[i] * A, (dis[i] / 2) * B + (dis[i] % 2) * A);
	for (int i = 1; i <= n; i++)
		vis[i] = 0;
	for (int i = 1; i <= n; i++)
		dis[i] = -1;
	q.push(S);
	vis[S] = 1;
	dis[S] = 0;
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		for (int i = 0; i < G1[t].size(); i++)
		{
			int v = G1[t][i];
			isedge[v] = 1;
		}
		for (int i = 0; i < G1[t].size(); i++)
		{
			int v = G1[t][i];
			auto it = G2[v].begin();
			while (it != G2[v].end())
			{
				if (isedge[*it]) it++;
				else
				{
					if (!vis[*it])
					{
						vis[*it] = 1;
						dis[*it] = dis[t] + 1;
						q.push(*it);
					}		
					it = G2[v].erase(it);
				} 
			}
		}
		for (int i = 0; i < G1[t].size(); i++)
		{
			int v = G1[t][i];
			isedge[v] = 0;
		}
	}
	for (int i = 1; i <= n; i++)
		if (dis[i] != -1) ans[i] = min(ans[i], dis[i] * B);
	for (int i = 1; i <= n; i++)	
		cout << ans[i] << endl;
	return 0;
}