牛客补题(BFS+DP)

96 阅读 0 评论 64 点赞

我是靠谱客的博主文艺皮皮虾，这篇文章主要介绍牛客补题(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
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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
*/