Don't use search algorithm,but Dynamic programming.Take cation that N is not very large,you can save all the nodes.