【LibreOJ】#6354. 「CodePlus 2018 4 月赛」最短路 异或优化建图+Dijkstra

【题目】#6354. 「CodePlus 2018 4 月赛」最短路
【题意】给定n个点，m条带权有向边，任意两个点i和j还可以花费(i xor j)*C到达（C是给定的常数），求A到B的最短距离。\(n \leq 10^5,m \leq 5*10^5\)。
【算法】异或优化建图+Dijkstra
正常建边O(n^{2)，与其考虑特殊边的处理不如考虑优化n}2的建边方案。一个点x到另一个点y的代价是由每个改变的数位得到的，所以枚举所有点x的每个数位j，从x向\(x \ \ xor \ \ 2^j\)连边代价为\(2^j\)。
复杂度\(O((m+n \ \ log \ \ n) \ \ log \ \ n)\)。

#include
#include
#include
#include
bool isdigit(char c){return c>='0'&&c<='9';}
int read(){
	int s=0,t=1;char c;
	while(!isdigit(c=getchar()))if(c=='-')t=-1;
	do{s=s*10+c-'0';}while(isdigit(c=getchar()));
	return s*t;
}
using namespace std;
const int maxn=100010,maxm=500010;
int tot,first[maxn],n,m,C,d[maxn];
struct edge{int v,w,from;}e[maxm+maxn*20];
void insert(int u,int v,int w){tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}
struct cyc{
	int d,id;
	bool operator < (const cyc &a)const{
		return d>a.d;
	}
};
priority_queueQ;
void dijkstra(int S){
	memset(d,0x3f,sizeof(d));
	d[S]=0;Q.push((cyc){0,S});
	while(!Q.empty()){
		cyc X=Q.top();Q.pop();
		int D=X.d,x=X.id;
		if(D!=d[x])continue;
		for(int i=first[x];i;i=e[i].from)if(d[x]+e[i].w