Untitled

 avatar
unknown
plain_text
2 years ago
1.0 kB
8
Indexable
#include<iostream>
using namespace std;

int front, rear, start, end, x, m, q; //m la so diem dung
int queue[10000], visit[1000], result[1000], ke[1000][1000];// ke la ma tran ke

void reset(){
	front=0;
	rear=0;
	for(int i=1; i<=m; i++){
		visit[i]=0;
		result[i]=0;
	}
}

void bfs(int a){
	reset();
	//them diem bat dau vao hang doi
	queue[rear]=a;
	rear++;
	visit[a]=1;
	
	while(front<rear){
		//khi hang doi van con phan tu
		//lay phan tu o dinh hang doi
		x=queue[front];
		front++;
		
		// neu la diem ket thuc thi dung bfs
		if(x==end) break;
		
		//xet cac diem neu ke voi diem dang xet va chua visit thi them vao hang doi
		for(int i=1; i<=m; i++){
			if(ke[x][i]==1 && visit[i]==0){
				queue[rear]=i;
				rear++;
				visit[i]=1;
				result[i]=result[x]+1;
			}
		}
	}

}


int main(){}
	
	//input
	//tao ma tran ke
	//xu ly
	while(q>0){
		cin>>start>>end;
		bfs(start);
		
		if(result[end]>3) cout<<0<<endl;
		else cout<<result[end]<<endl;
	}
	
}
Editor is loading...