題意：不用說了，中文題。
這個題可以用機率DP來做。
題中要求貓抓到老鼠的時間期望。分析一下這個過程，如果貓在每機關時間裡第一步移動沒有抓到老鼠，它還可以繼續移動一次。對于确定老鼠的位置，注意貓的每次移動都是固定的，而老鼠的移動位置卻是不定的。
令dp[i][j]表示貓在i位置老鼠在j位置時，貓抓到老鼠的期望。next[i][j]表示貓從i位置到j位置時走最短路徑需要移動到的第一個結點位置。d[i]表示結點i的度。
這樣首先看貓的目前位置，如果i==j即貓和老鼠在同一個點，那麼貓不用移動了這時候貓已經抓到了老師，dp[i][j]=0。
如果不等，考慮如果貓在這兩次移動中抓到了老鼠，如果貓第一步移動到了老鼠目前所在位置，即next[i][j]==j,或者貓第二步移動抓到了老鼠，即next[next[i][j]][j]==j,此時所用時間都是1，dp[i][j]=1。
其他情況，考慮貓在該機關時間内沒抓到老鼠，此時的狀态轉移取決于老鼠的行動。老鼠可以移動到任意一個和j結點相連的點，也可以停留在j點，每種情況發生的機率是1/(d[j]+1),每次轉移到的狀态即dp[next[next[i][j]][j]][k](k取值j,或與j點直接連邊的點），運用全期望公式即可。
這樣記憶化搜尋可解。
其中計算next[][]的過程可以用bfs預處理。
View Code
![在DOS下運作不了ipconfig指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)