标签：+# Code xor int 短路 times reads edge data
[$Code$+#4]最短路
链接:https://www.luogu.com.cn/problem/P4366
题面:给定一个$n$个点，$m$条边的无向图，若任意点对$(i,j)$之间还有一条长为$(i xor j)\times C$的边，求$A$到$B$的最短路。
题解:$(i xor j)\times C$这个式子看似很毒瘤，实际上我们可以把每一位拆开来看，若要从$9$走到$7$：
$((1001)_{2} xor (111)_{2})\times C$
$=(1000)_{2}\times C+(10)_{2}\times C+(100)_{2}\times C$
$=((1001)_{2}xor(1)_{2})\times C+((1)_{2}xor(11)_{2})\times C+((11)_{2}xor(111)_{2})\times C$
上述等式的含义即为$(1001)_{2}->(111)_{2}$等价于$(1001)_{2}->(1)_{2}->(11)_{2}->(111)_{2}$
推广即得,任意$(i,j)$的边，都可以被拆成若干个$(i,(i xor 2^t))$的边的权值和，每一个点$i$向$(i xor 2^t)$连边即可。
```
#include
#include
using namespace std;
struct node
{
int v,data,nxt;
};
struct reads
{
int num,data;
bool operator < (const reads &a)const
{
return data>a.data;
}
};
reads tmp;
priority_queueq;
node edge[4000001];
int head[200001],len,dis[200001],n,m,C;
bool used[200001];
void add(int x,int y,int z)
{
edge[++len].v=y;
edge[len].data=z;
edge[len].nxt=head[x];
head[x]=len;
return;
}
reads make_reads(int x,int y)
{
tmp.num=x;
tmp.data=y;
return tmp;
}
void dijkstra(int x)
{
q.push(make_reads(x,0));
for (int i=0;i<=n;++i)
dis[i]=(i!=x)*1e9;
int top;
while (!q.empty())
{
top=q.top().num;
q.pop();
if (used[top])
continue;
used[top]=1;
for (int i=head[top];i>0;i=edge[i].nxt)
if (dis[edge[i].v]>dis[top]+edge[i].data)
{
dis[edge[i].v]=dis[top]+edge[i].data;
q.push(make_reads(edge[i].v,dis[edge[i].v]));
}
}
}
int main()
{
int x,y,z,A,B;
cin>>n>>m>>C;
for (int i=1;i<=m;++i)
{
cin>>x>>y>>z;
add(x,y,z);
}
for (int i=0;i<=n;++i)
for (int k=1;k<=2*n;k*=2)
if ((i^k)<=n)
add(i,i^k,k*C);
cin>>A>>B;
dijkstra(A);
cout<
标签：+#,
Code,
xor,
int,
短路,
times,
reads,
edge,
data
From： https://www.cnblogs.com/zhouhuanyi/p/16983476.html