PAT A1076 Forwards on Weibo
此题本来没啥坑，用bfs记录层数并累加即可，然而之前写bfs记录层数是仿照姥姥讲的六度空间那个，貌似是用变量记录上一层的结尾值来控制level，但是dfs记录层数直接传参就行了，于是又一时冲动用了dfs(后来发现bfs也能同样用参数记录层数，只要在queue中push{序号，层数}的结构体就行了)。此题使用dfs就会遇到俩问题：1.正常的dfs每访问一个点就会置位相应的visited，之后这个点就变成了小小的窗扉紧掩，众人见到都会绕道而行，但事实上之后还有可能存在源点到此点有更短的路径，那么还应该能通过这个点继续向下一层走，所以这visited是个美丽的错误(有一个测试点因此wrong)2.若想解决第一个问题，首先想到是不用visited限制通行，如果这样的话，上面那个测试点过了，最后一个点会超时——很明显需要想办法剪枝(虽然这办法不是俺想出来的)。上面说了这个点开门的条件应该是之后遇到了更短的路径(其实也就是层数)，所以额外用一个数组记录每个点上一次的层数，当遇到访问过的点时，看看这次的层数是不是比上次的小，if yes则放行最后，不能直接开G[MAX][MAX]这种二维数组，否则最后一个点必超时
#include<iostream>
#include<vector>
using namespace std;
#define MAXSIZE 1010
#define INF 999999999
vector<int> G[MAXSIZE];
bool visited[MAXSIZE] = {false};
int layer[MAXSIZE];
int cnt = 0,L;
void dfs(int root,int level){
if(level == L + 1) return;
if(!visited[root]) cnt ++;
visited[root] = true;
layer[root] = level;
for(int i = 0;i < G[root].size();i ++){
int idx = G[root][i];
if(!visited[idx] || layer[idx] > level + 1) dfs(idx,level + 1);
}
}
int main(){
int num;
scanf("%d %d",&num,&L);
for(int i = 1;i <= num;i ++){
int n;
scanf("%d",&n);
for(int j = 0;j < n;j ++){
int k;
scanf("%d",&k);
G[k].push_back(i);
}
}
scanf("%d",&num);
for(int i = 1;i <= num;i ++){
int query;
scanf("%d",&query);
fill(visited,visited + MAXSIZE,false);
fill(layer,layer + MAXSIZE,L + 1);
cnt = 0;
dfs(query,0);
printf("%d\n",cnt - 1);
}
return 0;
}
Processed:
0.010, SQL:
9
