题解：P14128 [SCCPC 2021] Spicy Restaurant

· · 题解

题意：

在无向图中，对于每一次询问，寻找权值小于等于 a 的距离 p 最近的点，输出最短距离。

思路：

首先，我们看出这是一个最短路的题，但点数 n 和边数 m 都达到了 1\times10^5 的级别，所以普通的最短路算法肯定会 tle，需要优化。注意到辣度 w_i 的范围 \le100，因此我们可以对于每一个辣度跑一遍最短路，处理出每个点到每个辣度的最短距离，最后 O(1) 查询。

代码：

#include <bits/stdc++.h>
using namespace std;
int w[100005],dis[105][100005];
vector<int>tu[100005];
queue<int>qq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);//本题输入输出量较大，需要输入输出优化
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        tu[u].push_back(v);
        tu[v].push_back(u);//这里用vector存图
    }
    memset(dis,127,sizeof(dis));
    for(int i=1;i<=100;i++)
    {
        for(int j=1;j<=n;j++)
            dis[i][j]=dis[i-1][j];//这一步非常重要，题目中求的是辣度小于等于a的点的最短距离，不是等于a的最短距离，因此辣度高的点有可能继承辣度低的点的答案
        for(int j=1;j<=n;j++)
            if(w[j]==i)
            {
                dis[i][j]=0;//相等就修改为0
                qq.push(j);//入队
            }
        while(!qq.empty())
        {
            int x=qq.front();
            qq.pop();
            for(int j:tu[x])
                if(dis[i][j]>dis[i][x]+1)
                {
                    dis[i][j]=dis[i][x]+1;
                    qq.push(j);
                }
        }
    }//最短路模板
    while(q--)
    {
        int pos,a;
        cin>>pos>>a;
        int ans=dis[a][pos];
        cout<<(ans==2139062143?-1:ans)<<'\n';//这里的2139062143对应memset127之后的值
    }
    return 0;
}