40pts求条
查看原帖
40pts求条
1181602
Cute_Furina楼主2024/10/9 20:03
#include<bits/stdc++.h>
#define int long long
using namespace std;
priority_queue<pair<int, int> > a;
int cnt, ans, n, m, q;
int vis[100005], head[100005], edge[100005];
int nextt[100005], d[100005], v[100005];
void add(int x, int y, int z) {
	ans ++;
	vis[ans] = y;
	nextt[ans] = head[x];
	head[x] = ans;
	edge[ans] = z;
}
void dijkstra(int s) {
	for(int i = 0;i < 100005;i ++) v[i] = 0;
	for(int i = 0;i < 100005;i ++) d[i] = 0x7f;
	d[s] = 0;
	a.push(make_pair(0, s));
	while(a.size() != 0) {
		int x = a.top().second;
		a.pop();
		if(v[x] != 0) continue;
		v[x] = 1;
		for(int i = head[x];i != 0;i = nextt[i]) {
			int y = vis[i], z = edge[i];
			if(d[y] >= d[x] ^ z || cnt == m) {
				d[y] = d[x] ^ z;
				a.push(make_pair(-d[y], y));
			}
		}
	}
}
signed main() {
	cin >> n >> m >> q;
	for(int i = 1;i <= m;i ++) {
		int x, y, z;
		cin >> x >> y >> z;
		ans ++;
		vis[ans] = y;
		nextt[ans] = head[x];
		head[x] = ans;
		edge[ans] = z;
		ans ++;
		vis[ans] = x;
		nextt[ans] = head[y];
		head[y] = ans;
		edge[ans] = z;
		if(z <= 1) cnt ++;
	}
	dijkstra(1);
	for(int i = 1;i <= q;i ++) {
		int x, y;
		cin >> x >> y;
		cout << (d[x] ^ d[y]) << endl;
	}
	return 0;
}

2024/10/9 20:03
加载中...