CodeForces 845G

題面

題意

給出一張無向圖,求從1-n的所有路徑中的邊權X-or最短路.

做法

可以從環上來考慮,如果有環,那麼就一定可以0代價的異或這個環的權值,是以我們可以用dfs建出一棵搜尋樹,求出1到每個節點的距離,若找到環,則求出它與已經找到的環的異或最小值,非零則當作這個環的權值,記入已找到環的集合中,之後再求出1到n的距離與所有環的X-or最小值即可.

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#define N 100100
using namespace std;

int n,m,bb,first[N],d[N],ans;
bool vis[N];
struct Bn
{
    int to,next,quan;
}bn[N<<];
vector<int>vec;

inline void add(int u,int v,int w)
{
    bb++;
    bn[bb].to=v;
    bn[bb].quan=w;
    bn[bb].next=first[u];
    first[u]=bb;
}

inline void ad(int u)
{
    int i;
    for(i=;i<vec.size();i++)
    {
        u=min(u,vec[i]^u);
    }
    if(u) vec.push_back(u);
}

void dfs(int now,int last)
{
    vis[now]=;
    int p,q;
    for(p=first[now];p!=-;p=bn[p].next)
    {
        if(abs(p-last)==&&min(p,last)%) continue;
        if(vis[bn[p].to]) ad(d[now]^d[bn[p].to]^bn[p].quan);
        else d[bn[p].to]=d[now]^bn[p].quan,dfs(bn[p].to,p);
    }
}

int main()
{
    memset(first,-,sizeof(first));
    int i,j,p,q,o;
    cin>>n>>m;
    for(i=;i<=m;i++)
    {
        scanf("%d%d%d",&p,&q,&o);
        add(p,q,o),add(q,p,o);
    }
    dfs(,-);
    ans=d[n];
    for(i=;i<vec.size();i++)
    {
        ans=min(ans,ans^vec[i]);
    }
    cout<<ans;
}