Shortest Path With Constrains

I need to solve a graph, but with the a twist:

My problem is modeled by an edge-based graph (where each edge in the original graph is transformed into a vertex and each edge to edge "turn" is transformed into an edge).

Each edge in the original graph has multiple grades (in my specific case just two) and I have graded the turns as well. I want to minimize the cost of the solution path over one of the two grades of the edges. In addition, the other grade is a cumulative one and when it reaches a certain threshold it need to reset itself to 0 and this is achieved by taking certain "turns".

I have been searching for a shortest-path algorithm with constraints, but the problem is that the cumulative grade is based not only on the future vertices in the path, but as well in the past ones.

Could someone help me with this? A friend told me to try the A* prune algorithm (http://suraj.lums.edu.pk/~te/cspf/A_...Algorithmf.pdf) , but I haven't been able to make it work for me.

Thanks!
matigurten

I think you need to specify your problem better.

What's the significance of the transformation of the graph? What's a grade? What's the turns that are taken when a cumultative grade is resetting itself? What's to be solved?

In short, what exactly does the graph look like when the algorithm is applied and what is it supposed to accomplish?