1. 建一个状压dp数组,和两个邻接矩阵,一个备用数组(32768×15,15×1532768\times 15,15\times 1532768×15,15×15, 151515).
2. 如果在第一层,就求出11点与其他怪的距离.(矩阵2)
3. 如果不在第一层,将上一层的每个怪到下一层的怪表示出来.(矩阵2)
4. 直接广搜到每个怪,求出最短距离.(矩阵1)
5. 用备用数组计算跨层后(或从11点开始)加上状压dp最后一项的最短时间.
6. 压缩一波,清空dp数组并将 dp1,idp_{1,i}dp1,i 赋值为备用数组的第 iii 项.
7. 清空备用数组,状压dp.
如样例#1
第一层:
11建图:(矩阵2)
[15]\begin{bmatrix} 1\\ 5 \end{bmatrix}[15 ]
修改状压dp后的第一项:
[1,5][1,5][1,5]
广搜建图:(矩阵1)
[0440]\begin{bmatrix} 0&4\\ 4&0 \end{bmatrix}[04 40 ]
状压dp最后一项:[9,5][9,5][9,5]
第二层:
建跨层图:(矩阵2)
[2,4][2,4][2,4]
修改状压dp后的第一项:
[9][9][9]
广搜建图:略
状压dp最后一项:[9][9][9]
第三层:
建跨层图:(矩阵2)
[53]\begin{bmatrix} 5\\ 3 \end{bmatrix}[53 ]
修改状压dp后的第一项:
[14,12][14,12][14,12]
广搜建图:(矩阵1)
[0660]\begin{bmatrix} 0&6 \\ 6&0\end{bmatrix}[06 60 ]
状压dp最后一项:[20,18][20,18][20,18]
加上打怪的时间后为 343434.