原题
codeforces845G
题意
给一个无向带权图，求1-n的异或最短路。
解题思路
因为我们是在异或的情况下求最短路，因此环是一个特殊的存在。 我们从一个点走向环，在环内绕一圈再回到当前点，我们只会获得环的权值。也就是说，对于一个环的权值，我们可以只考虑选与不选。 如果我们在dfs遍历整个图的过程中，拆掉回边，图就成了一棵树。我们可以记录下i号点到1号点的异或距离d[i]，那么任意两个点u、v之间的距离可以用d[u]^d[v]表示。 假设在dfs的时候我们找到了一条连接u、v，权值为x的回边，相当于我们就找到了一个权值为d[u]^d[v]^x的环。 将环的权值放入线性基，答案相当于就是将d[n]与线性基内的数异或能取到的最小值。
代码
#include <cstdio>
using namespace std;
const int N=
1e5+
10;
struct Edge{
int to,next,cost; } way[N<<
1];
int n,m,tot,num[N];
bool vis[N];
struct Base
{
int x[
31];
void Insert(
int v)
{
if (!v)
return ;
for (
int i=
30;i>=
0;--i)
if ((
1<<i)&v)
{
if (x[i]) v^=x[i];
else { x[i]=v;
break; }
}
}
int Query(
int v)
{
for (
int i=
30;i>=
0;--i)
if ((v^x[i])<v) v^=x[i];
return v;
}
}base;
void AddEdge(
int a,
int b,
int c) { way[++tot]=(Edge){b,num[a],c}; num[a]=tot; }
void Init()
{
scanf(
"%d%d",&n,&m);
int u,v,cost;
for (
int i=
1;i<=m;++i)
{
scanf(
"%d%d%d",&u,&v,&cost);
AddEdge(u,v,cost);
AddEdge(v,u,cost);
}
}
int dis[N];
void Dfs(
int x)
{
vis[x]=
1;
for (
int i=num[x];i;i=way[i].next)
{
int v=way[i].to;
if (!vis[v])
{
dis[v]=dis[x]^way[i].cost;
Dfs(v);
}
else base.Insert(dis[v]^dis[x]^way[i].cost);
}
}
void Solve()
{
Dfs(
1);
printf(
"%d\n",base.Query(dis[n]));
}
int main()
{
Init();
Solve();
return 0;
}
