【题目】
【题意】给定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_queue Q;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