hdu6223 Infinite Fraction Path【bfs+剪枝】

先提取出最大的值放进优先队列里面

优先队列先按步数小的先排，步数相同的按值大的优先

剪枝:

当前位的值比队列出来的值大的直接忽略；

但前走的下标已经被走过了且当前步数小于最大步数直接忽略。

AC_code:

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define maxn 150005

int num[maxn];
ll Next[maxn];
int ans[maxn];
int mark[maxn];
struct node {
	int v;
	int next;
	int step;
	ndoe() {
	};
	node(int _v, int _next, int _step) {
		v = _v;
		next = _next;
		step = _step;
	}
};
struct cmp {
	bool operator() (const node &a, const node &b) const {
		if(a.step == b.step) {
			return a.v < b.v;
		}
		return a.step > b.step;
	}
};

priority_queue<node, vector<node>, cmp> q;


int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	int t;
	scanf("%d", &t);
	int cas = 1;
	while(t--) {
		int n;
		scanf("%d", &n);
		for(ll i = 0; i < n; i++) {
			scanf("%1d", &num[i]);
			Next[i] = (i*i+1)%n;
			mark[i] = -1;
			ans[i] = -1;
		}
		int maxx = -1;
		for(int i = 0; i < n; i++) {
			maxx = max(num[i], maxx);
		}
		for(int i = 0; i < n; i++) {
			if(num[i] == maxx) {
				q.push(node(maxx, i, 0));
			}
		}
		while(!q.empty()) {
			node temp = q.top();
			q.pop();
			if(ans[temp.step] == -1) {
				ans[temp.step] = temp.v;
			} else if(ans[temp.step] > temp.v) {
				continue;
			}

			if(mark[temp.next] < temp.step) {
				mark[temp.next] = temp.step;
			} else {
				continue;
			}
			if(temp.step == n-1) {
				continue;
			}
			q.push(node(num[Next[temp.next]], Next[temp.next], temp.step+1));
		}
		printf("Case #%d: ", cas++);
		for(int i = 0; i < n; i++) {
			printf("%d",ans[i]);
		}
		cout<<endl;
	}
}