Description：

给 $n$ 个点和 $m$ 条带权有向边，从点 $a$ 到 $b$ 可以走给出的 $m$ 条边，或者是花费 $(a\text{ xor }b)\times C$ 的代价直接到达，问从 $A$ 到 $B$ 的最短路。

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 5\times 10^5$

Solution：

直接做的边的个数是 $O(n^2)$ 的，最短路应该不会变，因为有 $m$ 条给定的边防止乱搞，肯定要减小图中的边数，分析一下会发现应该是有一些边可以用其他边替代或者是一定不会成为最优解中的边，对于一条边 $i\to j$ ，代价为 $i\text{ xor }j$ ，先不考虑 $C$ ，而我们知道 $i\text{ xor }j=i\text{ xor }k\text{ xor }k\text{ xor }j$ ，那是不是可以只保留与 $k$ 相关的边而舍弃 $i$ 和 $j$ 之间的边呢？发现要想这样做必须满足 $i\text{ xor }k\text{ xor }k\text{ xor }j=(i\text{ xor }k)+(k\text{ xor }j)$ ，由位运算的性质得这样必须满足 $i\text{ xor }k$ 和 $k\text{ xor }j$ 在二进制下 $1$ 的位互不相同，考虑怎么构造出这样一个情况，然后可以想到我们让 $i\text{ xor }k$ 二进制只有一个一，而 $k\text{ xor }j$ 这一位是 $0$ ，发现可以选出 $lowbit(i\text{ xor }j)$ ，这个一定在 $i$ 或 $j$ 其中一个为一，不妨假设是 $i$ ，那么就可以连边 $i\to i\text{ xor }lowbit(i\text{ xor }j)\to j$ ，把这个结论推广一下就会发现只有 $i$ 和 $i\text{ xor }2^k$ 的边是有用的，其他的都可以由它组合出，于是这样建边跑最短路就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,w;

int s,t;

#define MAXN 100010

#define MAXM 500010

struct edge

{

	int to,nxt,v;

}e[MAXM + MAXN * 17];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int v)

{

	e[++edgenum] = (edge){b,lin[a],v};lin[a] = edgenum;

	return;

}

int d[MAXN];

bool v[MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&w);

	R int a,b,c;

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

	{

		a = rd();b = rd();c = rd();

		add(a,b,c);

	}

	for(R int i = 0;i <= n;++i)

		for(R int k = 1;k <= n;k = k << 1)

			if((i ^ k) <= n)add(i,i ^ k,k * w);

	scanf("%d%d",&s,&t);

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

	d[s] = 0;

	priority_queue< pair<int,int> > q;

	q.push(make_pair(0,s));

	while(!q.empty())

	{

		R int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

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

		{

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

			{

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	printf("%d\n",d[t]);

	return 0;

}