牛客补题(BFS+DP)

Spicy Restaurant

题意
一个有n个节点m条边的无向图，每条边权值为1，每个节点有一个w值，有q次询问，每次询问从p点出发到达最近的一个w值不小于a的点的距离
思路：用bfs和dp进行打表，输入输出要用scanf和printf，不然会tle
代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<stack>
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
int t,n,m,q,dis[105][N],que[N*100];
vector<int> w[N];
vector<int> G[N];
void bfs(vector<int> &v,int x,int *dis){
int head=0,tail=0;
for(int i=1;i<=n;i++)
dis[i]=inf;
for(auto xx:v){
que[++tail]=xx;
dis[xx]=0;
}
while(tail!=head){
int qq=que[++head];
for(auto to:G[qq]){
if(dis[to]==inf){
dis[to]=dis[qq]+1;
que[++tail]=to;
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
int W,x,y;
for(int i=1;i<=n;i++){
scanf("%d",&W);
w[W].push_back(i);
}
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=100;i++){
bfs(w[i],i,dis[i]);
}
for(int i=2;i<=100;i++){
for(int j=1;j<=n;j++){
//dis[i][j]表示从j点出发,到达一个w值不超过i的最短距离
dis[i][j]=min(dis[i][j],dis[i-1][j]);
}
}
int p,a;
for(int i=1;i<=q;i++){
scanf("%d%d",&p,&a);
printf("%dn",dis[a][p]==inf?-1:dis[a][p]);
}
return 0;
}
/*
4 4 5
5 4 2 3
1 2
2 3
3 4
4 1
1 1
1 2
1 3
1 4
1 5
*/

最后

以上就是文艺皮皮虾为你收集整理的牛客补题(BFS+DP)的全部内容，希望文章能够帮你解决牛客补题(BFS+DP)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。