#include"cachable.h"
#include<iostream>
#include<unordered_map>

typedef unsigned long wtype;
typedef unsigned long ntype;


template<typename T>
void hashcomb(std::size_t &x, T &&v) {
	x ^= std::hash<typename std::remove_cv<
			typename std::remove_reference<T>::type>::type>()(v)
		+ 0x9e3779b9 + (x<<6) + (x>>2);
}

template<typename T1, typename T2>
struct pairhash : public std::unary_function<std::pair<T1,T2>,std::size_t> {
	std::size_t operator()(const std::pair<T1,T2> &p) const {
		std::size_t ret = std::hash<T1>()(p.first);
		hashcomb(ret,p.second);
		return ret;
	}
};


std::unordered_map<std::pair<ntype,ntype>,wtype,pairhash<ntype,ntype>> w
	{{{1,2},1},
      {{2,3},5},
      {{1,4},1},
      {{3,5},1},
      {{4,5},1},
      {{4,6},2}};

static wtype BIGVAL = 1000000LL;

/* Graph:
  
   1-(1)-2-(5)-3
   |          /
  (1)      (1)
   |      /
   4-(1)-5
   |
  (2)
   |
   6
*/

wtype edgeweight(ntype n1, ntype n2) {
	auto l = w.find({n1,n2});
	if (l!=w.end()) return l->second;
	l = w.find({n2,n1});
	if (l!=w.end()) return l->second;
	return BIGVAL;
}

long eval = 0;

std::function<wtype(ntype,ntype,ntype)> shortestpath = cachable::cachable(
	[](ntype n1, ntype n2, ntype m) -> wtype {
		eval++;
		if (m==0) return edgeweight(n1,n2);
		return std::min(shortestpath(n1,n2,m-1),
				shortestpath(n1,m,m-1)+shortestpath(m,n2,m-1));
	}
);

int main(int argc, char **argv) {
	std::cout << 
 "  1-(1)-2-(5)-3\n"
 "  |          /\n"
 " (1)      (1)\n"
 "  |      /\n"
 "  4-(1)-5\n"
 "  |\n"
 " (2)\n"
 "  |\n"
 "  6" << std::endl;
	while(!std::cin.eof()) {
		long peval = eval;
		ntype n1,n2;
		std::cin >> n1 >> n2;
		if (std::cin.eof()) break;
		std::cout << "short path length = " << shortestpath(n1,n2,6) << std::endl;
		std::cout << "number of evals = " << eval-peval << std::endl;
	}
}