[\(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<iostream>
#include<queue>
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_queue<reads>q;
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<<dis[B]<<endl;
return 0;
}
标签:+#,Code,xor,int,短路,times,reads,edge,data
From: https://www.cnblogs.com/zhouhuanyi/p/16983594.html