自动搬运

查看原文

来自洛谷，原作者为

	Clare613 Clare613小号一号||不要瞧不起绿名，绿名可以切绿题||开始时间：7.31，两个月上红名

搬运于2025-08-24 21:50:08，当前版本为作者最后更新于2025-08-13 17:00:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最早的一篇题解在 2017 年！

思路：

解决这道题之前，可以先去 P5663 写一下。
看到这道题，发现与 P5663 类似，断定为奇偶最短路，区别在于起点的地方变了。
我们知道，奇偶最短路就是将 SPFA 按照奇数偶数两条路走。原因是不同的步数对应不同的路，长度不难分为奇数和偶数，把 P5663 的模板偷过来，接着向下看。
我们先采取在线输出，发现：

int cnt[5005][5005][2];

于是 MLE 就喜欢上了你。
那么就用离线，将 int cnt[5005][5005][2]; 缩为 int cnt[5005][2]; 后对于相同起点的询问一并处理。将这一步完成后发现 $88$ 分，就剩一个特判：独立点或不连接块答案为 NIE，于是就 AC 了。

code：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int v,w;
	bool operator < (const node &a) const{
		return a.w<w;
	}
};
bool cmp(node x,node y){
	return x.w<y.w;
}
struct poblem{
	int t,d,id;
};
vector<poblem> q[5005];
vector<int> g[5005];
int cnt[5005][2];
string ans[1000005];
int n,m,k;
bool fff[5005][2];
void dij(int id){
	for(int i=1;i<=n;i++){
		fff[i][0]=fff[i][1]=0;
		cnt[i][0]=cnt[i][1]=1e9;
	}
	queue<node> q;
	q.push({id,0});
	cnt[id][0]=1;
	while(!q.empty()){
		node t=q.front();
		q.pop();
		for(auto i:g[t.v]){
			if(cnt[i][(t.w+1)%2]>t.w+1){
				cnt[i][(t.w+1)%2]=t.w+1;
				q.push({i,cnt[i][(t.w+1)%2]});
			}
		}
	}
	cnt[id][0]=0;
}
int fa[5005],f[5005];
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0)->sync_with_stdio(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
		fa[find(x)]=find(y);
		f[x]=f[y]=1;
	}
	for(int i=1;i<=k;i++){
		int s,t,d;
		cin>>s>>t>>d;
		q[s].push_back({t,d,i});
	}
	for(int i=1;i<=n;i++){
		if(q[i].size()==0) continue;
		dij(i);
		for(auto j:q[i]){
			if(cnt[j.t][j.d%2]>j.d){
				ans[j.id]="NIE\n";
			}
			else if(j.t==i||cnt[j.t][j.d%2]!=0){
				ans[j.id]="TAK\n";
			}
			else{
				ans[j.id]="NIE\n";
			}
		}
	}
	for(int i=1;i<=k;i++){
		cout<<ans[i];
	}
	return 0;
}
/*

*/