| 设dp[i,j,k]表示时间i，猫在j，老鼠在k时，猫平均还需要多少步吃掉老鼠。dp[i,j,k]=∑dp[i+1,xj,ku]/(en+1)+1，其中xj是猫走两步（或一步）后的位置，ku是包括k在内所有与k相连的点，en是k的出度。为了求猫的位置，预处理时作一次ASSP（原来想的是Dijkstra+Heap优化，后来发现只要BFS就可以了）即可。但时间复杂度是O(n^3)。注意到在推节点的过程中，如果在某一时间猫和老鼠分别在tc,tm，那么在以后的时间，猫和老鼠不会再在tc,tm，否则猫永远不会捉到老鼠。那么在设计状态的时候就没有必要考虑时间。设dp[i,j]表示猫在i，老鼠在j时，猫平均还需要几步可以吃掉老鼠。于是有：dp[i,j]=∑dp[xi,ju]/(en+1)+1这样时间复杂度降到O(n^2) |