专栏文章

题解：P11591 [NordicOI 2024] Anime Shops

eemoni
P11591题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8fwek
此快照首次捕获于
2025/12/01 22:16
3 个月前
此快照最后确认于
2025/12/01 22:16
3 个月前
查看原文

Solution

纯暴力思路。不知道为什么能过还跑得飞快。感觉可以被卡到 O(n2)O(n^2)。可能是我不会算时间复杂度的问题吧 /yun。
为叙述方便，以下称有动漫商店的点为黑点，其它为白点。
我们可以对于 kk 个黑点都进行一次 BFS，找到其它每个点与它的距离。一个很难注意不到的且很有效的剪枝是：对于每一个节点，若其当前的最近距离 disudis_u 小于等于此次 BFS 当前的 stepstep，那么我们不再让其入队。正确性显然。而且非常非常好写。
然而，我这么写，获得了零分的好成绩！
零分代码CPP
#include<bits/stdc++.h>
using namespace std;

int n,m,k,a[100005];
vector<int> e[100005];
struct node{
	int u,step;
};
queue<node> q;
int dis[100005];
int vis[100005];

void bfs(int st){
	while(!q.empty())
		q.pop();
	q.push({st,0});
	vis[st]=st;
	while(!q.empty()){
		int u=q.front().u,step=q.front().step;
		q.pop();
//		cout<<u<<" "<<dis[u]<<endl;
		for(auto v:e[u]){
			if(dis[v]<=step+1||vis[v]==st)
				continue;
			dis[v]=step+1;
			q.push({v,step+1});
			vis[v]=st;
		}
	}
	return;
}

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=k;i++)
		bfs(a[i]);
	for(int i=1;i<=n;i++)
		if(dis[i]==0x3f3f3f3f) cout<<-1<<" ";
		else cout<<dis[i]<<" ";
	return 0;	
}
求助于全知全能聪慧过人的 JACK0927为什么我的暴力没有 TLE 但是 WA，于是他送了我一个 hack，大家快去膜拜他！
hack
hack.in
CPP
9 9 2
1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 1
hack.out
CPP
3 1 2 3 2 1 3 1 1
零分代码输出：
CPP
-1 1 2 3 2 1 3 1 1
检查代码发现，这个算法不能很好地处理黑点。以上述 hack 为例：在以 11 号点为初始节点 BFS 时，11 号点自身没有被更新，dis8=1dis_8=1。在以 77 号点为初始节点 BFS 时，当搜索到 88 号点，step=1step=1，不小于 dis8dis_8，于是不将 88 号点加入搜索队列，于是不能用 77 号点更新 11 号点，导致 11 号点答案未被记录。
考虑如何高效简便地解决这一问题。
我们在 BFS 时，用 faifa_i 记下距离 ii 最近的黑点。在以另一黑点 ss 为起点 BFS 搜索到 ii 时，尝试用 disi+step+1dis_i+step+1 更新 disfaidis_{fa_i}，即用当前黑点 ss 更新另一黑点 uu。正确性也显然。
于是我们解决了这一问题。
CodeCPP
#include<bits/stdc++.h>
using namespace std;

int n,m,k,a[100005],f[100005];
vector<int> e[100005];
struct node{
	int u,step;
};
queue<node> q;
int dis[100005],fa[100005];
int vis[100005];

void bfs(int st){
	while(!q.empty())
		q.pop();
	q.push({st,0});
	vis[st]=st;
	while(!q.empty()){
		int u=q.front().u,step=q.front().step;
		q.pop();
		for(auto v:e[u]){
			if(dis[v]!=0x3f3f3f3f&&fa[v]!=st)
				if(dis[v]+step+1<dis[fa[v]]){
					dis[fa[v]]=dis[v]+step+1;
					fa[fa[v]]=st;
				}
			
			if(dis[v]<=step+1||vis[v]==st)
				continue;
			dis[v]=step+1;
			fa[v]=st;
			q.push({v,step+1});
			vis[v]=st;
		}
	}
	return;
}

int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++)
		cin>>a[i],f[a[i]]=1;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=k;i++)
		bfs(a[i]);
	for(int i=1;i<=n;i++)
		if(dis[i]==0x3f3f3f3f) cout<<-1<<" ";
		else cout<<dis[i]<<" ";
	return 0;	
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...