1 solutions

  • 0
    @ 2023-3-5 14:16:32

    只是一道bfs的板子,十分标准,放在这次周赛就可以看出平时训练哪些同学没认真

    在广度优先搜索中,要想发现与起点s距离为k+1的顶点,首先要发现所有与距离为k的顶点,因此可以依次求出起点到个顶点的最短距离。

    如下述算法所示,广度优先搜索会将各顶点v到s的距离记录在d[v]中。

    广度优先搜索:

    1.将起点s放入队列Q(访问)。

    2.只要Q不为空,就循环执行如下处理。

    ·从Q取出顶点u进行访问(访问结束) ·将与u相邻的未访问顶点v放入Q,同时将d[v]更新为d[u]+1

    代码如下

    #include<iostream>
    #include<queue>
    
    using namespace std;
    static const int N = 100;
    static const int INFTY = (1<<21);
    
    int n, M[N][N];
    int d[N]; //通过距离管理访问状态(color)
    
    void bfs(int s) {
    	queue<int> q;//使用标准库中的queue
    	q.push(s);
    	for(int i=0;i<n;i++)d[i]=INFTY;
    	d[s]=0;
    	int u;
    	while(!q.empty()){
    		u=q.front();q.pop();
    		for(int v=0;v<n;v++){
    			if(M[u][v]==0)continue;
    			if(d[v]!=INFTY)continue;
    			d[v]=d[u]+1;
    			q.push(v);
    		}
    	} 
    	for(int i=0;i<n;i++){
    		cout<<i+1<<" "<<((d[i]==INFTY)?(-1):d[i])<<endl;
    	}
    } 
    
    int main(){
    	int u,k,v;
    	
    	cin>>n;
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++)M[i][j]=0;
    	}
    	
    	for(int i=0;i<n;i++){
    		cin>>u>>k;
    		u--;
    		for(int j=0;j<k;j++){
    			cin>>v;
    			v--;
    			M[u][v]=1;
    		}
    	}
    	
    	bfs(0);
    	
    	return 0;
    }
    

    Information

    ID
    6700
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    41
    Accepted
    14
    Uploaded By