题解：P14128 [SCCPC 2021] Spicy Restaurant

· · 题解

题目大意

给出一个 n 个点 m 条边的无向连通图，每个点都有其相应的点权 w_i。

一共 q 次询问，第 i 次求出离节点 p_i 最近的一个权值不大于 a_i 的节点的距离（每条边的权值固定为 1），若无解输出 -1。

分析

观察到 q 的范围比 n 和 m 都要大，这也就导致我们直接模拟是不可行的，所以我们可以预处理。

又很容易观察到 w_i 和 a_i 其实都很小，即 1\le w_i,a_i\le 100。于是乎，我们便可以直接枚举范围内的所有辣度。对于每一种辣度，都去预处理出它对于所有点的答案。

边权都为 1 的话，求最短路不需要很复杂，直接用 BFS 搜索即可。

代码细节

其实本题的 BFS 是多源 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
    }
}

最后提醒一下，若使用链式前向星存图一定要开双倍空间（双向边）。

AC code:

#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;
}