这个40分暴力哪错了啊…求救
查看原帖
这个40分暴力哪错了啊…求救
573589
ande楼主2022/6/14 22:18

RT

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200 + 7;
typedef pair<int, int> P;
int n, m, T, ans;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
struct aa{
	int to, next, weigh;
}edge[N*2];

int head[N], t = 1;
void add(int now, int to, int w){
	edge[t].to = to;
	edge[t].next = head[now];
	edge[t].weigh = w;
	head[now] = t++;
}

int DP[N], mp[N];

void dijk(int s){
	priority_queue<P, vector<P>, greater<P> > pq;
	for(int i= 1;i <= n; i++)
		DP[i] = 0x7f7f, mp[i] = 0;
	DP[s] = 0;
	pq.push({0, s});

	while(!pq.empty()){
		P p = pq.top(); pq.pop();
		int now = p.second;
		if(mp[now] == 1){
			continue;
		}
		mp[now] = 1;
		for(int i = head[now]; i ; i = edge[i].next){
			int to_ = edge[i].to, w = edge[i].weigh;
			// printf(" %d %d ",DP[to_],DP[now] ^ w);
			if(DP[to_] > (DP[now] ^ w)){
				// cout<<"!";
				DP[to_] = DP[now] ^ w;
				pq.push({DP[to_], to_});
		}
		// printf(" %d ",DP[to_]);
	}
}
return ;	
}
int main() {
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
n = read(); m = read(); T = read();
for(int i = 1;i <= m;i++){
	int a = read(), b = read(), z = read();
	add(a, b, z), add(b,a,z);
}
for(int i=1;i<=T;i++){
	int x = read(), y = read();
	dijk(x);
	printf("%d\n",DP[y]);
}
return 0;

}
// 4 3 1
// 1 2 1
// 2 3 2
// 3 4 3
// 1 4
2022/6/14 22:18
加载中...