专栏文章

题解：P14128 [SCCPC 2021] Spicy Restaurant

mmengnn
P14128题解参与者 1已保存评论 0

文章操作

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

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

题目大意

给出一个 nn 个点 mm 条边的无向连通图，每个点都有其相应的点权 wiw_i。
一共 qq 次询问，第 ii 次求出离节点 pip_i 最近的一个权值不大于 aia_i 的节点的距离（每条边的权值固定为 11），若无解输出 -1。

分析

观察到 qq 的范围比 nn 和 mm 都要大，这也就导致我们直接模拟是不可行的，所以我们可以预处理。
又很容易观察到 wiw_i 和 aia_i 其实都很小，即 1≤wi,ai≤1001\le w_i,a_i\le 100。于是乎，我们便可以直接枚举范围内的所有辣度。对于每一种辣度，都去预处理出它对于所有点的答案。
边权都为 11 的话，求最短路不需要很复杂，直接用 BFS 搜索即可。

代码细节

其实本题的 BFS 是多源 BFS，因为要从所有符合条件的点出发，直接将所有点同时入队即可：
CPP
queue<pair<int,int> > q;
//队列，pair 的第一关键字为节点编号，第二关键字为路径长度
for (int i=1;i<=n;i++){
    vis[i]=false;//初始化 vis 数组
    if (a[i]<=mx){//如果节点辣度能被接受
        vis[i]=true;
        q.push({i,0});
        dp[i][mx]=0;
        //从此节点出发进行 BFS
    }
}
最后提醒一下，若使用链式前向星存图一定要开双倍空间（双向边）。

AC code:

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
//注意：要开双倍空间（双向边）
int vtx[N],nxt[N],hed[N],tot;//链式前向星数组
int n,m,q,a[N],dp[N][105];
//如题所述，不同的是 a[i] 存的是点权，dp[i][j] 存的是答案（位于第 i 个点能接受的最大辣度为 j 时的答案）
bool vis[N];
//BFS 是否访问过
inline void addedge(int u,int v){//链式前向星存图（建边）
	vtx[++tot]=v;
	nxt[tot]=hed[u];
	hed[u]=tot;
}
inline void add(int u,int v){//建双向边
	addedge(u,v);
	addedge(v,u);
}
inline void bfs(int mx){//核心 BFS
	queue<pair<int,int> > q;
	//队列，pair 的第一关键字为节点编号，第二关键字为路径长度
	for (int i=1;i<=n;i++){
		vis[i]=false;//初始化 vis 数组
		if (a[i]<=mx){//如果节点辣度能被接受
			vis[i]=true;
			q.push({i,0});
			dp[i][mx]=0;
			//从此节点出发进行 BFS
		}
	}
	while (!q.empty()){
		int x=q.front().first;
		int s=q.front().second;//最短路
		q.pop();
		//弹出队首元素
		for (int j=hed[x];j;j=nxt[j]){//链式前向星遍历
			int y=vtx[j];
			if (!vis[y]){
				vis[y]=true;
				q.push({y,s+1});
				dp[y][mx]=s+1;
				//入队，继续更新答案
			}
		}
	}
}
int main(){
    cin>>n>>m>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1,x,y,z;i<=m;i++){
    	cin>>x>>y;
    	add(x,y);
    }//以上都是输入
    //把 dp 数组初始化为极大值
    memset(dp,0x7f,sizeof(dp));
    //预处理所有辣度并求最短路
    for (int i=1;i<=100;i++) bfs(i);
    while (q--){
    	int p,w;cin>>p>>w;
    	//直接输出即可，注意要判断无解情况，即超过 n 次都到不了
    	cout<<(dp[p][w]>n?-1:dp[p][w])<<'\n';
    }
    return 0;
}

评论

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

正在加载评论...