Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:优不优先队列都能AC,不过注意下两个相等的情况。WA了无数次才发现

Posted by 3096947160 at 2022-03-12 12:18:37 on Problem 3278
In Reply To:优不优先队列都能AC,不过注意下两个相等的情况。WA了无数次才发现 Posted by:qq1250173534 at 2020-03-01 19:50:27
> #include <iostream>
> #include <cstring>
> #include <cstdio>
> #include <algorithm>
> #include <queue>
> #include <cmath>
> using namespace std;
> const int maxn = 1e5+10;
> struct node{
> 	int x;			//当前点的坐标
> 	int t;			//时间
> 	bool operator <(const node s)const{
> 		return s.t < t;
> 	} 
> };
> priority_queue<node>q;
> bool visited[maxn];
> void bfs(int k)
> {
> 	while(!q.empty()){
> 		node p = q.top(),ptr;
> 		q.pop();
> 		if(p.x == k){
> 			printf("0\n");
> 			return ;
> 		}
> 		for(int i = 0;i < 3;i++){
> 			if(i == 0){
> 				ptr.x = p.x + 1;
> 			}
> 			if(i == 1){
> 				ptr.x = p.x - 1;
> 			}
> 			if(i == 2){
> 				ptr.x = p.x * 2;
> 			}
> 			if(ptr.x < 0 || ptr.x > maxn || visited[ptr.x] == true){
> 				continue;
> 			} 
> 			ptr.t = p.t + 1;
> 			if(ptr.x == k){
> 				printf("%d\n",ptr.t);
> 				return ;
> 			}
> 			visited[ptr.x] = true;
> 			q.push(ptr);
> 		}
> 	}
> }
> int main()
> {
> 	int n,k;
> 	while(~scanf("%d%d",&n,&k)){
> 		memset(visited,false,sizeof(visited));
> 		while(!q.empty()){
> 			q.pop();
> 		}
> 		node p;
> 		p.x = n;p.t = 0;
> 		q.push(p);
> 		visited[n] = true;
> 		bfs(k);
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator