LGOJ P5651 基础最短路练习题

LGOJ P5651 基础最短路练习题

注意到，保证G中不存在简单环使得边权异或和不为0。

也就是说，如果某两点存在多条路径，无论这个路径是怎样走最终的异或和都是相同的。

这意味着我们可以把边权转化为点权。

这样，路径长度\(d\)的定义（用$\oplus $表示异或：
\[ d(u,v)= w_1 \oplus w_2 \oplus ... \oplus w_n, \quad w_i(i \in [1,n]) \in d \]
就可以转化为：
\[ d(u,v)= v_1 \oplus v_2 \oplus v_2 \oplus v_3 \oplus v_3 \oplus v_4 \oplus ... \oplus v_{n-1} \oplus v_{n-1} \oplus v_n, \quad v_i(i \in [1,n]) \in d \\Downarrow\d(u,v)= v_1 \oplus v_n \]
dfs一次性求完所有\(v_i\),Q次询问每次\(O(1)\);

时间复杂度是线性的不错。

#include <bits/stdc++.h>
#define ll int
using namespace std;
const int  N=1e5+245;
inline ll read()
{
    char c=getchar();ll x=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
        x=x*10+c-'0';
    return x;
}

ll n,m,q;
struct node
{
    ll v,w;
    node(ll a,ll b)
    {
        v=a;
        w=b;
    }
};
vector<node> G[N];
ll val[N];
bool vis[N];

void dfs(int u)
{
    for(int i=0;i<G[u].size();i++)
    {
        ll v=G[u][i].v,w=G[u][i].w;
        if(vis[v]==0)
        {
            vis[v]=1;
            val[v]=val[u]^w;
            dfs(v);
        }
    }
}


int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        ll u=read();
        ll v=read();
        ll w=read();
        G[u].push_back(node(v,w));
        G[v].push_back(node(u,w));
    }
    vis[1]=1;
    dfs(1);
    for(int i=1;i<=q;i++)
    {
        ll u=read();
        ll v=read();
        printf("%d\n",val[u]^val[v]);
    }

    return 0;
}

LGOJ P5651 基础最短路练习题

原文：https://www.cnblogs.com/kion/p/11855745.html