50分求助!!!!
查看原帖
50分求助!!!!
647610
ZwhY111楼主2022/10/27 11:15
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <queue>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 1e6 + 10, INF = 1e9;
int h[N], e[N], w[N], ne[N], dist[N], idx;
bool st[N];
int n, m, q;

void add(int a, int b, int c)
{
    w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}


void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    dist[1] = 0;
    heap.push({0, 1});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > (distance ^ w[i]))
            {
                dist[j] = distance ^ w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m >> q;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    dijkstra();

    while(q --)
    {
        int x, y;
        cin >> x >> y;
        cout << (dist[x] ^ dist[y]) << endl;
    }

    return 0;
}

2022/10/27 11:15
加载中...