2017 G icpc shenyang Infinite Fraction Path BFS + pruning

The meaning of the question: Given a string array of length n, you can select the starting point to jump n times, from point i can only jump to the position of (i*i+1)%n, and finally find a maximum lexicographical order.

Ideas: The largest number is required, that is, each step is the largest, so the largest number is entered into the team for bfs to jump to the next step.

Pruning: 1. If the point jumping to the next step is smaller than other points jumping to the next step, remove it

2. If there are two points that reach the same point through the same synchronization number, then their subsequent states are also the same, so they are also eliminated.

ok, it is all.

First we use a structure to wrap the number of steps and the position pos node{step,pos}

Use the nex array to represent the value of the number from the pos point to the next position

Then we customize a sorting function in the priority queue (the most important pruning is actually the sorting method)

If the value of step and the next step nex[pos] are equal, we sort by pos from small to large

If step is equal, nex[pos] is not equal, according to nex[pos] from big to small

If the steps are not equal, follow the steps from small to large

Pit!!!Pay attention to i*i burst int, disgusting

#include#include#include#include#include#include#include#include#include