Suppose you have a maze represented by a graph where each vertex represents a room and edges represent paths between rooms and each edge has a weight denoting the time it takes to go that way. Now here comes the tricky part: suppose each room needs a set of keys for you to enter, and inside each room you can find another set of keys. Keys can be repeated and one key may be needed to enter on more than one room. You can only enter the room if you have all keys required.
You have an arbitrarily large number of chests with gold inside and each chest needs one key which can be found in the maze. You already have a set of keys that you can use. You can use a key more than once. The question is: how do you collect the keys you need as fast as possible?
The only algorithm I could come up with was to have as state keys you have and node, so it'd be O(2numberofkeys * numberofhalls)
This problem is NP-hard. Let G = (V, E) be a graph. Put a different key in each room and one cheast for each key. Then the answer is |V| if and only if the graph has a Hamiltonian path. So there is no polynomial time algorithm for your problem unless P=NP.