0分求助!
查看原帖
0分求助!
727871
lizhehao2009楼主2024/5/30 20:10
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    ll first,second,distance;
};
struct edge
{
    ll id,distance;
};
node a[200010];
vector<edge> road[200010];
ll father[200010],ans;
bool vis[200010],flag;
ll get(ll x)
{
    if (father[x]==x)
    {
        return x;
    }
    return father[x]=get(father[x]);
}
bool cmp(node x,node y)
{
    return x.distance<y.distance;
}
void dfs(ll x,ll y,ll sum)
{
    if (flag==false||vis[x]==1)
    {
        return;
    }
    if (x==y)
    {
        flag=false;
        ans=sum;
        return;
    }
    vis[x]=1;
    for (ll i=0;i<road[x].size();i++)
    {
        dfs(road[x][i].id,y,sum^road[x][i].distance);
    }
}
int main()
{
    ll n,m,q,x,y,v,a1,a2;
    scanf("%lld%lld%lld",&n,&m,&q);
    for (ll i=1;i<=n;i++)
    {
        father[i]=i;
    }
    for (ll i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&v);
        a[i].first=x;
        a[i].second=y;
        a[i].distance=v;
    }
    sort(a+1,a+m+1,cmp);
    for (ll i=1;i<=m;i++)
    {
        a1=get(a[i].first);
        a2=get(a[i].second);
        if (a1!=a2)
        {
            father[a2]=a1;
            road[a[i].first].push_back(edge{a[i].second,a[i].distance});
            road[a[i].second].push_back(edge{a[i].first,a[i].distance});
        }
    }
    while (q--)
    {
        scanf("%lld%lld",&x,&y);
        flag=true;
        memset(vis,0,sizeof(vis));
        dfs(x,y,0);
        printf("%lld\n",ans);
    }
    return 0;
}
2024/5/30 20:10
加载中...